Problem: 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

Solution (in PYTHON3):

Solution:
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
        
        used = [False]*self.N
        TF = [None]*self.N
        for c in components:
            for ci in c:
                cin = ci % self.N
                if used[cin]:
                    continue
                if ci != cin:
                    TF[cin] = True
                else:
                    TF[cin] = False
                used[cin] = True  
        return TF
                
        
    
    
N, D = map(int, readline().split())

TS = two_sat(2*N)
for i in range(N):
    TS.add_edge(0, i, 1, N+i)
    TS.add_edge(0, N+i, 1, i)

Flags = [tuple(map(int, readline().split())) for _ in range(N)]

for i in range(N):
    x, y = Flags[i]
    for j in range(N):
        if i == j:
            continue
        u, v = Flags[j]
        if abs(x-u) < D:
            TS.add_edge(1, i, 0, j)
        if abs(x-v) < D:
            TS.add_edge(1, i, 0, N+j)
        if abs(y-u) < D:
            TS.add_edge(1, N+i, 0, j)
        if abs(y-v) < D:
            TS.add_edge(1, N+i, 0, N+j)

A = TS.solve()
Ans = [None]*N
if A != -1:
    print('Yes')
    for i in range(N):
        if A[i]:
            Ans[i] = Flags[i][0]
        else:
            Ans[i] = Flags[i][1]
    print('\n'.join(map(str, Ans)))
else:
    print('No')