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 PYTHON):

Solution:
import sys
range = xrange
input = raw_input
 
def find_SCC(coupl):
    SCC, S, P = [], [], []
    depth = [0] * len(coupl)
 
    stack = list(range(len(coupl)))
    while stack:
        node = stack.pop()
        if node < 0:
            d = depth[~node] - 1
            if P[-1] > d:
                SCC.append(S[d:])
                del S[d:], P[-1]
                for node in SCC[-1]:
                    depth[node] = -1
        elif depth[node] > 0:
            while P[-1] > depth[node]:
                P.pop()
        elif depth[node] == 0:
            S.append(node)
            P.append(len(S))
            depth[node] = len(S)
            stack.append(~node)
            stack += coupl[node]
    return SCC[::-1]

class TwoSAT:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(2 * n)]

    def _imply(self, x, y):
        self.graph[x].append(y if y >= 0 else 2 * self.n + y)

    def either(self, x, y):
        """either x or y must be True"""
        self._imply(~x, y)
        self._imply(~y, x)

    def set(self, x):
        """x must be True"""
        self._imply(~x, x)

    def solve(self):
        SCC = find_SCC(self.graph)
        
        inSCC = [0] * (2 * self.n)
        for scc_ind, scc in enumerate(SCC):
            for node in scc:
                inSCC[node] = scc_ind
        
        for i in range(self.n):
            if inSCC[i] == inSCC[~i]:
                return False, None
        
        return True, [+(inSCC[i] < inSCC[~i]) for i in range(self.n)]

inp = [int(x) for x in sys.stdin.read().split()]; ii = 0
 
n = inp[ii]; ii += 1
d = inp[ii]; ii += 1

sat = TwoSAT(n)

X = inp[ii + 0: ii + 2 * n: 2] 
Y = inp[ii + 1: ii + 2 * n: 2] 
ii += 2 * n

for i in range(n):
    for j in range(i + 1, n):
        
        if abs(X[i] - X[j]) < d:
            sat.either(i, j)
        
        if abs(Y[i] - Y[j]) < d:
            sat.either(~i, ~j)
        
        if abs(X[i] - Y[j]) < d:
            sat.either(i, ~j)
        
        if abs(Y[i] - X[j]) < d:
            sat.either(~i, j)

exists, solution = sat.solve()

if not exists:
    print 'No'
else:
    print 'Yes'
    print ' '.join(str(X[i] if b else Y[i]) for i, b in enumerate(solution))