Description

Farmer John has $N$ ($2\le N\le 1000$) cows at distinct locations $l_1,\dots, l_N$ along a circle of circumference $C$ ($0\le l_1 < l_2 < \dots < l_N <C, N\le C\le 10^9$).

FJ will select $k$ pairs of cows, where $1\le k\le \lfloor N/2\rfloor$, and no cow is selected more than once. He wants to select the pairs such that the minimum distance between any two cows in the same pair along the circumference of the circle is maximized.

For each value of $k$, help FJ determine the maximum possible minimum distance.

Input Format

The first line contains $N$ and $C$.

The second line contains $l_1\dots l_N$.

Output Format

Output a single line with $\lfloor N/2\rfloor$ space-separated integers, with the answers for $k=1\dots \lfloor N/2\rfloor$ in that order.

4 100
0 25 50 75

50 50

4 100
0 1 2 99

3 2

Hint

Sample 1 Explanation

For $k = 1$, cow 1 can be paired to cow 3, which is distance $50$ away along the circumference of the circle, making the answer $50$.

For $k = 2$, cow 1 can be paired to cow 3, and cow 2 can be paired to cow 4, which is distance $50$ away from it along the circumference of the circle, making the answer still $50$.

Sample 2 Explanation

For $k = 1$, cow 3 can be paired to cow 4, which is distance $2 + 100 - 99 = 3$ away from it along the circumference of the circle, making the answer $3$.

For $k = 2$, cow 1 can be paired to cow 3 and cow 2 can be paired to cow 4. Each of these pairs contains two cows at a distance of $2$ from each other along the circumference of the circle, making the answer $2$.

SCORING:

• Inputs 3-4: $2l_N \le C$
• Inputs 5-6: $N\le 20$
• Inputs 7-14: $N\le 100$
• Inputs 15-22: No additional constraints.