题目描述

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$ 和一个非负整数 $k$，你可以最多执行以下操作一次：选择两个整数 $l$ 和 $r$（满足 $1 \leq l \leq r \leq n$），然后将区间 $[l, r]$ 内的每个元素 $a_i$  替换为 $a_i + k$。请最大化操作后整个序列的最大公约数$（GCD）$。定义：若整数 $g$ 是整个序列的公约数，则对于所有 $1 \leq i \leq n$，$a_i$ 能被 $g$ 整除。

输入格式

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 3 \times 10^5$，$0 \leq k \leq 10^{18}$）。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^{18}$），表示序列。

输出格式

输出一行一个整数，表示操作后序列的最大可能最大公约数。

样例

输入

6 2  
5 3 13 8 10 555  

5

输入

3 0  
3 6 9

3

样例解释

第一个测试用例中，选择区间 ([2, 4])，操作后的序列为 ({5, 5, 15, 10, 10, 555})，其最大公约数为 5。第二个测试用例中，(k = 0)，操作不会改变序列，原序列的最大公约数为 3。

限制与约定

对于 $40\%$的样例，保证 $1 \leq n \leq 100$，$0 \leq k \leq 100$。$1 \leq a_i \leq 10^5$

对于 $100\%$的样例，保证 $1 \leq n \leq 3 \times 10^5$，$0 \leq k \leq 10^{18}$。$1 \leq a_i \leq 10^{18}$

• 时间限制: $1 s$
• 空间限制: $256 MB$