103622: [Atcoder]ABC362 C - Sum = 0

Problem Statement

You are given $N$ pairs of integers $(L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N)$.

Determine whether there exists a sequence of $N$ integers $X = (X_1, X_2, \ldots, X_N)$ that satisfies the following conditions, and print one such sequence if it exists.

• $L_i \leq X_i \leq R_i$ for each $i = 1, 2, \ldots, N$.
• $\displaystyle \sum_{i=1}^N X_i = 0$.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $-10^9 \leq L_i \leq R_i \leq 10^9$
• All input values are integers.

Input

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

$N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

Output

If no solution exists, print No. Otherwise, print an integer sequence $X$ that satisfies the conditions in the following format:

Yes
$X_1$ $X_2$ $\ldots$ $X_N$

If multiple solutions exist, any of them will be considered correct.

Sample Input 1

3
3 5
-4 1
-2 3

Sample Output 1

Yes
4 -3 -1

The sequence $X = (4, -3, -1)$ satisfies all the conditions. Other valid sequences include $(3, -3, 0)$ and $(5, -4, -1)$.

Sample Input 2

3
1 2
1 2
1 2

Sample Output 2

No

No sequence $X$ satisfies the conditions.

Sample Input 3

6
-87 12
-60 -54
2 38
-76 6
87 96
-17 38

Sample Output 3

Yes
-66 -57 31 -6 89 9

问题陈述

给你N对整数$(L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N)$。

判断是否存在一个由N个整数组成的序列$X = (X_1, X_2, \ldots, X_N)$满足以下条件，如果存在则输出这样一个序列。

• 对于每个$i = 1, 2, \ldots, N$，有$L_i \leq X_i \leq R_i$。
• $\displaystyle \sum_{i=1}^N X_i = 0$。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $-10^9 \leq L_i \leq R_i \leq 10^9$
• 所有输入值都是整数。

输入

输入从标准输入以下格式给出：

$N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

输出

如果没有解决方案，打印No。否则，打印一个满足条件的整数序列$X$，以下列格式：

Yes
$X_1$ $X_2$ $\ldots$ $X_N$

如果有多个解决方案，任何一个都算正确。

示例输入1

3
3 5
-4 1
-2 3

示例输出1

Yes
4 -3 -1

序列$X = (4, -3, -1)$满足所有条件。其他有效的序列包括$(3, -3, 0)$和$(5, -4, -1)$。

示例输入2

3
1 2
1 2
1 2

示例输出2

No

没有序列$X$满足条件。

示例输入3

6
-87 12
-60 -54
2 38
-76 6
87 96
-17 38

示例输出3

Yes
-66 -57 31 -6 89 9