和为 0

题目描述

给定 $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 \le X_i \le R_i$。
• $\displaystyle \sum_{i=1}^N X_i = 0$。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

若不存在解,输出 No。否则,按以下格式输出满足条件的整数序列 $X$:

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

若存在多个解,输出其中任意一个即可。

样例

3
3 5
-4 1
-2 3

Yes
4 -3 -1

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

3
1 2
1 2
1 2

No

不存在满足条件的序列 $X$。

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

Yes
-66 -57 31 -6 89 9

数据范围

• $1 \le N \le 2 \times 10^5$
• $-10^9 \le L_i \le R_i \le 10^9$
• 所有输入值均为整数。

提示

答案不唯一,输出任意合法解即可。