問題文

正整数列 $A = (A_1, A_2, \\ldots, A_N)$ および正整数 $X$ が与えられます。あなたはこの数列に対して、次の操作を何度でも行うことができます（$0$ 回でもよい）：

• 添字 $i$ （$1\\leq i\\leq N$）および、$0\\leq x\\leq X$ となる非負整数 $x$ を選ぶ。$A_i$ を $2A_i+x$ に変更する。

操作結果の $\\max\\{A_1,A_2,\\ldots,A_N\\}-\\min\\{A_1,A_2,\\ldots,A_N\\}$ としてありうる最小値を求めてください。

制約

• $2\\leq N\\leq 10^5$
• $1\\leq X\\leq 10^9$
• $1\\leq A_i\\leq 10^9$

---

入力

入力は以下の形式で標準入力から与えられます。

$N$ $X$ $A_1$ $A_2$ $\\ldots$ $A_N$

出力

操作結果の $\\max\\{A_1,A_2,\\ldots,A_N\\}-\\min\\{A_1,A_2,\\ldots,A_N\\}$ としてありうる最小値を出力してください。

---

入力例 1

4 2
5 8 12 20

出力例 1

6

$A_i$ を $2A_i+x$ に変更する操作を $(i, x)$ と表すことにします。最適な操作列の一例は次の通りです。

• $(1,0)$, $(1,1)$, $(2,2)$, $(3,0)$

操作結果は $A = (21, 18, 24, 20)$ となり、$\\max\\{A_1,A_2,A_3,A_4\\}-\\min\\{A_1,A_2,A_3,A_4\\} = 6$ が達成できます。

---

入力例 2

4 5
24 25 26 27

出力例 2

0

最適な操作列の一例は次の通りです。

• $(1,5)$, $(1,5)$, $(2,5)$, $(2,1)$, $(3,2)$, $(3,3)$, $(4,0)$, $(4,3)$

操作結果は $A = (111,111,111,111)$ となり、$\\max\\{A_1,A_2,A_3,A_4\\}-\\min\\{A_1,A_2,A_3,A_4\\} = 0$ が達成できます。

---

入力例 3

4 1
24 25 26 27

出力例 3

3

一度も操作を行わないことにより、$\\max\\{A_1,A_2,A_3,A_4\\}-\\min\\{A_1,A_2,A_3,A_4\\} = 3$ が達成できます。

---

入力例 4

10 5
39 23 3 7 16 19 40 16 33 6

出力例 4

13