問題文

高橋くんは、長さ L の横に長いケーキを持っています。 このケーキの左端から距離 x の点を、座標 x の点と呼ぶことにします。 最初、このケーキの上には 1 つだけイチゴが置かれていて、その座標は X です。

高橋くんはこれから、N 回の操作を行います。 具体的には、i (0 \leq i \leq N-1) 回目の操作では以下のことをします。

• 座標 A_i にイチゴが置かれていない場合: 座標 A_i にイチゴを置く。
• 座標 A_i にイチゴが置かれている場合: 座標 A_i にあるイチゴを取り除く。

なお、それぞれの操作のあと、ケーキの上に 2 つ以上のイチゴが置かれていることが保証されます。

あるケーキの美しさを、以下のように定義します。

• 次の操作を何回でも自由に行えるとした時、「最も近い 2 つのイチゴの間の距離」としてありうる最大の値がケーキの美しさになる。
  • 座標 x に置かれているイチゴを、座標 L-x に移動する。なお、移動先に別のイチゴが置かれている場合は操作を行えない。

全ての i (0 \leq i \leq N-1) について、i 回目の操作のあとのケーキの美しさを求めてください。 なお、ケーキの美しさを求める際に、実際にイチゴを動かすことはありません。

制約

• 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
• 全ての i (0 \leq i \leq N-1) について、i 回目の操作のあとにケーキの上に 2 つ以上のイチゴが置かれている。
• 入力される値はすべて整数である。

入力例 1

5 10 0
6
9
3
0
3

出力例 1

6
4
3
3
5

例えば、1 回目の操作が終わった時、ケーキの上には 3 つのイチゴが置かれており、その座標は 0,6,9 です。 座標 6 にあるイチゴを座標 4 に動かすと、イチゴの座標は 0,4,9 になります。 このとき、「最も近い 2 つのイチゴの間の距離」は 4 になり、これが最大です。 よって、このケーキの美しさは 4 です。

入力例 2

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

出力例 2

7
3
2
3
3
1
1
3
3
1