Vasya 的生日即将到来,他的妈妈决定给他一个长度为 n 的正整数 a 数组。
Vasya 认为数组的美在于其所有元素的最大公约数。当然,他的妈妈想给他一个尽可能漂亮的阵列(尽可能美丽)。不幸的是,店里只剩下一排了。从好的方面来说,卖家说他可以减少数组中的一些数字(每个数字最多减少 k)。
如果满足以下条件,卖方可以从数组a中获取数组b:bi > 0; 对于所有 1 ≤ i ≤ n,0 ≤ ai - bi ≤ k。
帮助妈妈找到她送给 Vasya 的阵列的最大可能的美丽(卖家可以获得)。
输入
第一行包含两个整数 n 和 k (1 ≤ n ≤ 3·105; 1 ≤ k ≤ 106)。第二行包含 n 个整数 ai (1 ≤ ai ≤ 106) — 数组 a。
输出
在单行中打印一个数字——结果数组的最大可能的美感。
示例
输入 #1
6 1 3 6 10 12 13 16
输出 #1
3
输入 #2
5 3 8 21 52 15 77
输出 #2
7
注意
在第一个示例中我们可以获得数组:
3 6 9 12 12 15
在第二个示例中,我们可以获得下一个数组:
7 21 49 14 77