Problem Description

Takahashi has a long horizontal cake of length $ L $. We will call the point at distance $ x $ from the left end of the cake the point with coordinate $ x $. Initially, there is one strawberry on the cake, and its coordinate is $ X $.

Takahashi will perform $ N $ operations. Specifically, in the $ i $ -th ($0 \leq i \leq N-1$) operation, he will do the following:

• If there is no strawberry at coordinate $ A_i $: Place a strawberry at coordinate $ A_i $.
• If there is a strawberry at coordinate $ A_i $: Remove the strawberry at coordinate $ A_i $.

After each operation, it is guaranteed that there are at least two strawberries on the cake.

The beauty of a cake is defined as follows:

• The maximum possible value of the distance between the two closest strawberries, assuming you can perform the following operation any number of times:
• Move the strawberry at coordinate $ x $ to coordinate $ L-x $. Note that you cannot perform this operation if there is another strawberry at the destination coordinate.

For each $ i $ ($0 \leq i \leq N-1$), find the beauty of the cake after the $ i $ -th operation. Note that you do not actually move the strawberries when calculating the beauty.

Input Format

The input is given from the standard input in the following format:

$ N $ $ L $ $ X $ $ A_0 $ $ A_1 $ $\vdots$ $ A_{N-1} $

Output Format

Output $ N $ lines. The $ i+1 $ -th ($0 \leq i \leq N-1$) line should contain the beauty of the cake after the $ i $ -th operation.

Sample Input and Output

Sample Input #1

5 10 0
6
9
3
0
3

Sample Output #1

6
4
3
3
5

Sample Input #2

10 10 7
10
2
6
2
10
4
1
4
10
3

Sample Output #2

7
3
2
3
3
1
1
3
3
1

Notes/Hints

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq L \leq 10^9$
• $0 \leq X \leq L$
• $0 \leq A_i \leq L$
• For all $ i $ ($0 \leq i \leq N-1$), there are at least two strawberries on the cake after the $ i $ -th operation.
• All input values are integers.

Sample Explanation 1

For example, after the first operation, there are three strawberries on the cake with coordinates $ 0, 6, 9 $. If you move the strawberry at coordinate $ 6 $ to coordinate $ 4 $, the coordinates of the strawberries become $ 0, 4, 9 $. The distance between the two closest strawberries is $ 4 $, which is the maximum possible. Therefore, the beauty of the cake is $ 4 $.

见题面 Input 部分

见题面 Output 部分