Problem Statement

You are given $a sequence A = (A_1, A_2, \ldots, A_N)$ of positive integers and a positive integer X.
You can perform the operation below any number of times, possibly zero:

• Choose an index $i (1\leq i\leq N)$ and a non-negative integer x such that $0\leq x\leq X. Change A_i$ to 2A_i+x.

Find the smallest possible value of $\max$${A_1,A_2,\ldots,A_N$$}-\min$${A_1,A_2,\ldots,A_N$} after your operations.

Input

Input is given from Standard Input in the following format:
N X
$A_1 A_2 \ldots A_N$

Output

Print the smallest possible value of $\max$${A_1,A_2,\ldots,A_N$$}-\min$${A_1,A_2,\ldots,A_N$} after your operations.

Constraints

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

Sample Input 1

4 2
5 8 12 20

Sample Output 1

6

Let (i, x) denote an operation that changes A_i to 2A_i+x. An optimal sequence of operations is

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

which yields $A = (21, 18, 24, 20), achieving \max${A_1,A_2,A_3,A_4$}-\min${A_1,A_2,A_3,A_4} = 6.

Sample Input 2

4 5
24 25 26 27

Sample Output 2

0

An optimal sequence of operations is

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

which yields $A = (111,111,111,111), achieving \max${A_1,A_2,A_3,A_4$}-\min${A_1,A_2,A_3,A_4} = 0.

Sample Input 3

4 1
24 25 26 27

Sample Output 3

3

Performing no operations achieves $\max${A_1,A_2,A_3,A_4$}-\min${A_1,A_2,A_3,A_4} = 3.

Sample Input 4

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

Sample Output 4

13

见题面 Input 部分

见题面 Output 部分