B - Minimize Abs 1 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) 及び整数 L,R が与えられます。ここで L,R は L\leq R を満たします。

i=1,2,\ldots,N について以下の 2 つの条件を共に満たす整数 X_i を求めてください。なお、求める整数は常に一意に定まります。

  • L\leq X_i \leq R
  • L 以上 R 以下であるようなどの整数 Y についても |X_i - A_i| \leq |Y-A_i| を満たす

制約

  • 1\leq N\leq 2\times 10^5
  • 1\leq L\leq R \leq 10^9
  • 1\leq A_i\leq 10^9
  • 入力は全て整数

入力

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

N L R
A_1 \ldots A_N

出力

i=1,2,\ldots,N について X_i を空白区切りで出力せよ。

入力例 1

5 4 7
3 1 4 9 7

出力例 1

4 4 4 7 7

i=1 では、

  • |4-3|=1
  • |5-3|=2
  • |6-3|=3
  • |7-3|=4

より X_i = 4 です。

入力例 2

3 10 10
11 10 9

出力例 2

10 10 10

Score : 200 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N and integers L and R such that L\leq R.

For each i=1,2,\ldots,N, find the integer X_i that satisfies both of the following conditions. Note that the integer to be found is always uniquely determined.

  • L\leq X_i \leq R.
  • For every integer Y such that L \leq Y \leq R, it holds that |X_i - A_i| \leq |Y - A_i|.

Constraints

  • 1\leq N\leq 2\times 10^5
  • 1\leq L\leq R \leq 10^9
  • 1\leq A_i\leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N L R
A_1 \ldots A_N

Output

Print X_i for i=1,2,\ldots,N, separated by spaces.

Sample Input 1

5 4 7
3 1 4 9 7

Sample Output 1

4 4 4 7 7

For i=1:

  • |4-3|=1
  • |5-3|=2
  • |6-3|=3
  • |7-3|=4

Thus, X_i = 4.

Sample Input 2

3 10 10
11 10 9

Sample Output 2

10 10 10