题目描述

正整数列 $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\} $ としてありうる最小値を求めてください。

输入格式

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

$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\} $ としてありうる最小値を出力してください。

题目大意

你有一个正整数序列 $A$ 和一个整数 $x$。你可以任意次把某个 $A_i$ 变成$2A_i + v(0 \leq v \leq x)$。求出 $ \max\{A_1,A_2,\ldots,A_N\}-\min\{A_1,A_2,\ldots,A_N\} $ 的最小值。

4 2
5 8 12 20

6

4 5
24 25 26 27

0

4 1
24 25 26 27

3

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

13

提示

制約

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

Sample Explanation 1

$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 $ が達成できます。

Sample Explanation 2

最適な操作列の一例は次の通りです。 - $(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 $ が達成できます。

Sample Explanation 3

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