Contest Duration: - (local time) (100 minutes) Back to Home
C - Sum = 0 /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

N 個の整数の組 (L_1,R_1),(L_2,R_2),\ldots,(L_N,R_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


### 出力

Yes
X_1 X_2 \ldots X_N


### 入力例 1

3
3 5
-4 1
-2 3


### 出力例 1

Yes
4 -3 -1


### 入力例 2

3
1 2
1 2
1 2


### 出力例 2

No


### 入力例 3

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


### 出力例 3

Yes
-66 -57 31 -6 89 9


Score : 350 points

### 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