Consider placing N flags on a line. Flags are numbered through 1 to N.

Flag i can be placed on the coordinate X_i or Y_i. For any two different flags, the distance between them should be at least D.

Decide whether it is possible to place all N flags. If it is possible, print such a configulation.

Constraints

• $1 \leq N \leq 1000$
• $0 \leq D \leq 10^9$
• $0 \leq X_i < Y_i \leq 10^9$
• All values in Input are integer.

Input

Input is given from Standard Input in the following format:

N D
X_1 Y_1
X_2 Y_2
$\vdots$
X_N Y_N

Output

Print No if it is impossible to place N flags.

If it is possible, print Yes first. After that, print N lines. i-th line of them should contain the coodinate of flag i.

Examples

Input

3 2
1 4
2 5
0 6

Output

Yes
4
2
0

Input

3 3
1 4
2 5
0 6

Output

No

见题面

见题面