103301: [Atcoder]ABC330 B - Minimize Abs 1

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

问题描述

给你一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$，以及两个整数 $L$ 和 $R$，满足 $L\leq R$。

对于每个 $i=1,2,\ldots,N$，找到满足以下两个条件的整数 $X_i$。请注意，要找的整数总是唯一确定的。

• $L\leq X_i \leq R$。
• 对于满足 $L \leq Y \leq 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$

输出

以空格分隔的方式打印 $X_i$，对于 $i=1,2,\ldots,N$。

样例输入 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