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:
from collections import defaultdict


class TwoSat:
    def __init__(self, N):
        self.N = 2*N
        self.ans = None
        self.__e = []
        self.__v = list(range(self.N))

    def add_clause(self, i, f, j, g):
        self.__e.append((2*i + (0 if f else 1), 2*j + (1 if g else 0)))
        self.__e.append((2*j + (0 if g else 1), 2*i + (1 if f else 0)))

    @staticmethod
    def scc(V, E):
        g = defaultdict(list)
        rg = defaultdict(list)
        for u, v in E:
            g[u].append(v)
            rg[v].append(u)

        o = []
        done = set()
        for u in V:
            if u in done:
                continue

            s = [(u, True)]
            while s:
                u, f = s.pop()
                if f:
                    if u in done:
                        continue
                    done.add(u)
                    s.append((u, False))
                    for v in g[u]:
                        if v in done:
                            continue
                        s.append((v, True))
                else:
                    o.append(u)

        done = set()
        ans = []
        while o:
            u = o.pop()
            if u in done:
                continue

            s = [u]
            vv = [u]
            done.add(u)
            while s:
                u = s.pop()
                for v in rg[u]:
                    if v in done:
                        continue
                    vv.append(v)
                    s.append(v)
                    done.add(v)
            ans.append(vv)

        return ans

    def satisfiable(self):
        scc = TwoSat.scc(self.__v, self.__e)
        cid = [-1] * (self.N)

        for i, s in enumerate(scc):
            for v in s:
                cid[v] = i

        for i in range(self.N//2):

            if cid[2*i] == cid[2*i+1]:
                self.ans = None
                return False

        self.ans = []
        for i in range(self.N//2):
            self.ans.append(cid[2*i] < cid[2*i+1])

        return True


def atcoder_practice2_h():
    N, D = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(N)]

    ts = TwoSat(N)
    for i, (x1, y1) in enumerate(XY):
        for j in range(i+1, N):
            x2, y2 = XY[j]
            if abs(x1 - x2) < D:
                ts.add_clause(i, False, j, False)

            if abs(y1 - y2) < D:
                ts.add_clause(i, True, j, True)

            if abs(x1 - y2) < D:
                ts.add_clause(i, False, j, True)

            if abs(y1 - x2) < D:
                ts.add_clause(i, True, j, False)

    if not ts.satisfiable():
        print('No')
    else:
        print('Yes')
        for i, b in enumerate(ts.ans):
            print(XY[i][0 if b else 1])


if __name__ == "__main__":
    atcoder_practice2_h()