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:
def scc(E):
    n = len(E)
    iE = [[] for _ in range(n)]
    for i, e in enumerate(E):
        for v in e:
            iE[v].append(i)
    T = []
    done = [0] * n # 0 -> 1 -> 2
    ct = 0
    for i0 in range(n):
        if done[i0]: continue
        Q = [~i0, i0]
        while Q:
            i = Q.pop()
            if i < 0:
                if done[~i] == 2: continue
                done[~i] = 2
                T.append(~i)
                ct += 1
                continue
            if i >= 0:
                if done[i]: continue
                done[i] = 1
            for j in E[i]:
                if done[j]: continue
                Q.append(~j)
                Q.append(j)
    
    done = [0] * n
    SCC = []
    ### ID が必要なとき
    I = [0] * n
    ###
    for i0 in T[::-1]:
        if done[i0]: continue
        L = []
        Q = [~i0, i0]
        while Q:
            i = Q.pop()
            if i < 0:
                if done[~i] == 2: continue
                done[~i] = 2
                L.append(~i)
                ###
                I[~i] = len(SCC)
                ###
                continue
            if i >= 0:
                if done[i]: continue
                done[i] = 1
            for j in iE[i]:
                if done[j]: continue
                Q.append(~j)
                Q.append(j)
        SCC.append(L)
    return SCC, I

    ### ↓ Edge が必要なとき （上の return を消す）
    nE = [set() for _ in range(len(SCC))]
    for i, e in enumerate(E):
        for j in e:
            if I[i] == I[j]: continue
            # print("i, j, I[i], I[j] =", i, j, I[i], I[j])
            nE[I[i]].add(I[j])
    nE = [list(e) for e in nE]
    return SCC, I, nE

class twosat():
    def __init__(self, n):
        self.n = n
        self.E = [[] for _ in range(n * 2)]
    def add_clause(self, i, f, j, g):
        assert 0 <= i < self.n
        assert f == 0 or f == 1
        assert 0 <= j < self.n
        assert g == 0 or g == 1
        self.E[i * 2 + (f ^ 1)].append(j * 2 + g)
        self.E[j * 2 + (g ^ 1)].append(i * 2 + f)
    
    def satisfiable(self):
        SCC, I = scc(self.E)
        re = [0] * self.n
        for i in range(self.n):
            if I[2*i] == I[2*i+1]: return (0, [])
            if I[2*i] < I[2*i+1]: re[i] = 1
        return (1, re)

N, D = map(int, input().split())
ts = twosat(N)
X = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append((x, y))

for i, (x1, y1) in enumerate(X):
    for j, (x2, y2) in enumerate(X[:i]):
        if abs(x1 - x2) < D:
            ts.add_clause(i, 1, j, 1)
        if abs(x1 - y2) < D:
            ts.add_clause(i, 1, j, 0)
        if abs(y1 - x2) < D:
            ts.add_clause(i, 0, j, 1)
        if abs(y1 - y2) < D:
            ts.add_clause(i, 0, j, 0)

a, sa = ts.satisfiable()
if a == 0:
    print("No")
else:
    print("Yes")
    print(*[x[r] for x, r in zip(X, sa)], sep = "\n")