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
input = sys.stdin.readline
n, d = map(int,input().split())
C = [list(map(int,input().split())) for i in range(n)]

def dfs_numbering(st, M, V, ANS, cnt, v):
    ST = [st]
    while len(ST) > 0:
        i = ST[-1]
        if ANS[i] == -1:
            V[i] = v
            end = 1
            for x in M[i]:
                if V[x] == -1:
                    ST.append(x)
                    end = 0
            if end == 1:
                ST.pop()
                ANS[i] = cnt
                cnt += 1
        else:
            ST.pop()
    return cnt

class scc():  # 有向グラフを強連結成分分解（互いに行き来できる領域ごとに区切る）する。
    def __init__(self, n):  # 頂点数nのグラフを作成
        self.n = n
        self.M = [[] for i in range(n)]
        self.IM = [[] for i in range(n)]

    def add_edge(self, frm, to):  # frm->toの辺を追加
        self.M[frm].append(to)
        self.IM[to].append(frm)

    def scc_list(self):  # 連結成分ごとの頂点リストを返す
        n = self.n
        V = [-1] * n
        ANS = [-1] * n

        cnt = 0
        for i in range(n):
            if V[i] == -1:
                cnt = dfs_numbering(i, self.M, V, ANS, cnt, 0)

        ANS1 = [[ANS[i], i] for i in range(n)]
        ANS1.sort(reverse=True)

        V = [-1] * n
        ANS = [-1] * n
        v = 0
        for i in range(n):
            if V[ANS1[i][1]] == -1:
                dfs_numbering(ANS1[i][1], self.IM, V, ANS, 0, v)
                v += 1

        FANS = [[] for i in range(v)]
        for i in range(n):
            FANS[V[i]].append(i)

        return FANS

class twosat():
    def __init__(self, n):
        self.n = n
        self.S = scc(2*n)
        self.ANS = [True] * n

    def add_clause(self, i, f, j, g):
        fb = (int(f) + 1) % 2
        gb = (int(g) + 1) % 2
        self.S.add_edge(2*i + fb, 2*j + g)
        self.S.add_edge(2*j + gb, 2*i + f)

    def satisfiable(self):
        n = self.n
        sl = self.S.scc_list()
        A = [-1] * (2*n)
        for i in range(len(sl)):
            for j in range(len(sl[i])):
                A[sl[i][j]] = i
        
        for i in range(n):
            if A[2*i] == A[2*i+1]:
                return False
            self.ANS[i] = A[2*i] < A[2*i+1]
        return True

    def answer(self):
        return self.ANS

T = twosat(n)
for i in range(n):
    for j in range(i+1, n):
        # print(i,j)
        for k in range(2):
            for l in range(2):
                if abs(C[i][k] - C[j][l]) < d:
                    # print(i, (k+1)%2, j, (l+1)%2)
                    T.add_clause(i, (k+1)%2, j, (l+1)%2)

sa = T.satisfiable()
if sa:
    print("Yes")
    ANS = T.answer()
    for i in range(n):
        print(C[i][int(ANS[i])])
else:
    print("No")