human
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
Solve the task in PYTHON3.
assistant
#Here is Python code to print `No` if it is impossible to place N flags.

import sys
readline = sys.stdin.readline

class two_sat:
    def __init__(self, N):
        self.N = N
        self.Edge = [[] for _ in range(N*2)]
    
    def add_edge(self, t1, p1, t2, p2):
        # (not if t1 == 0) p1 ==> (not if t2 == 0) p2
        self.Edge[(1-t1)*self.N + p1].append((1-t2)*self.N + p2)
        
    def solve(self):
        N = len(self.Edge)
        Edgeinv = [[] for _ in range(N)]
        for vn in range(N):
            for vf in self.Edge[vn]:
                Edgeinv[vf].append(vn)
        
        used = [False]*N
        dim = [len(self.Edge[i]) for i in range(N)]
        order = []
        for st in range(N):
            if not used[st]:
                stack = [st, 0]
                while stack:
                    vn, i = stack[-2], stack[-1]   
                    if not i and used[vn]:
                        stack.pop()
                        stack.pop()
                    else:
                        used[vn] = True
                        if i < dim[vn]:
                            stack[-1] += 1
                            stack.append(self.Edge[vn][i])
                            stack.append(0)
                        else:
                            stack.pop()
                            order.append(stack.pop())
        res = [None]*N
        used = [False]*N
        cnt = -1
        for st in order[::-1]:
            if not used[st]:
                cnt += 1
                stack = [st]
                res[st] = cnt
                used[st] = True
                while stack:
                    vn = stack.pop()
                    for vf in Edgeinv[vn]:
                        if not used[vf]:
                            used[vf] = True
                            res[vf] = cnt
                            stack.append(vf)
        M = cnt+1
        components = [[] for _ in range(M)]
        for i in range(N):
            components[res[i]].append(i)
        
        for i in range(self.N):
            if res[i] == res[self.N+i]:
                return -1
    ...