Two SAT

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

inputFormat

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

outputFormat

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

样例

3 3
1 4
2 5
0 6

No