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:
class CSR:
    def __init__(self, n: int, edges: list):
        self.start = [0] * (n + 1)
        self.elist = [0] * len(edges)
        for e in edges:
            self.start[e[0] + 1] += 1

        for i in range(1, n + 1):
            self.start[i] += self.start[i - 1]

        counter = self.start[::]  # copy
        for e in edges:
            self.elist[counter[e[0]]] = e[1]
            counter[e[0]] += 1


class SccGraph:
    def __init__(self, n: int = 0):
        self.__n = n
        self.__edges = []

    def __len__(self):
        return self.__n

    def add_edge(self, s: int, t: int):
        assert 0 <= s < self.__n and 0 <= t < self.__n
        self.__edges.append([s, t])

    def scc_ids(self):
        g = CSR(self.__n, self.__edges)
        now_ord = group_num = 0
        visited = []
        low = [0] * self.__n
        order = [-1] * self.__n
        ids = [0] * self.__n
        parent = [-1] * self.__n
        for root in range(self.__n):
            if order[root] == -1:
                stack = [root, root]
                while stack:
                    v = stack.pop()
                    if order[v] == -1:
                        visited.append(v)
                        low[v] = order[v] = now_ord
                        now_ord += 1
                        for i in range(g.start[v], g.start[v + 1]):
                            t = g.elist[i]
                            if order[t] == -1:
                                stack += [t, t]
                                parent[t] = v
                            else:
                                low[v] = min(low[v], order[t])

                    else:
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[u] = self.__n
                                ids[u] = group_num
                                if u == v:
                                    break

                            group_num += 1

                        if parent[v] != -1:
                            low[parent[v]] = min(low[parent[v]], low[v])

        for i, x in enumerate(ids):
            ids[i] = group_num - 1 - x

        return group_num, ids

    def scc(self):
        """
        強連結成分のリストを返す。この時、リストはトポロジカルソートされている
        [[強連結成分のリスト], [強連結成分のリスト], ...]
        """
        group_num, ids = self.scc_ids()
        counts = [0] * group_num
        for x in ids:
            counts[x] += 1

        groups = [[] for _ in range(group_num)]
        for i, x in enumerate(ids):
            groups[x].append(i)

        return groups


class TwoSAT():
    def __init__(self, n):
        self.n = n
        self.res = [0]*self.n
        self.scc = SccGraph(2*n)

    def add_clause(self, i, f, j, g):
        # assert 0 <= i < self.n
        # assert 0 <= j < self.n
        self.scc.add_edge(2*i + (not f), 2*j + g)
        self.scc.add_edge(2*j + (not g), 2*i + f)

    def satisfiable(self):
        """
        条件を足す割当が存在するかどうかを判定する。割当が存在するならばtrue、そうでないならfalseを返す。
        """
        group_num, ids = self.scc.scc_ids()
        for i in range(self.n):
            if ids[2*i] == ids[2*i + 1]: return False
            self.res[i] = (ids[2*i] < ids[2*i+1])
        return True

    def result(self):
        """
        最後に呼んだ satisfiable の、クローズを満たす割当を返す。
        """
        return self.res



#############################################################################

import sys
input = sys.stdin.buffer.readline

N, D = map(int, input().split())
XY = []
for _ in range(N):
    X, Y = map(int, input().split())
    XY.append((X, Y))
ts = TwoSAT(N)
for i in range(N-1):
    x0, y0 = XY[i]
    for j in range(i+1, N):
        x1, y1 = XY[j]
        if abs(x0 - x1) < D:
            ts.add_clause(i, 1, j, 1)
        if abs(x0 - y1) < D:
            ts.add_clause(i, 1, j, 0)
        if abs(y0 - x1) < D:
            ts.add_clause(i, 0, j, 1)
        if abs(y0 - y1) < D:
            ts.add_clause(i, 0, j, 0)

if ts.satisfiable():
    print('Yes')
    print('\n'.join(map(str, (xy[r] for r, xy in zip(ts.result(), XY)))))
else:
    print('No')