実行時間制限: 2 sec / メモリ制限: 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