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:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline
    from collections import deque

    # compressed[v]: 縮約後のグラフで縮約前のvが属する頂点
    # num: 縮約後のグラフの頂点数
    # 縮約後のグラフの頂点番号はトポロジカル順
    def SCC(adj, adj_rev):
        N = len(adj) - 1
        seen = [0] * (N + 1)
        compressed = [0] * (N + 1)
        order = []

        for v0 in range(1, N + 1):
            if seen[v0]:
                continue
            st = deque()
            st.append(v0)
            while st:
                v = st.pop()
                if v < 0:
                    order.append(-v)
                else:
                    if seen[v]:
                        continue
                    seen[v] = 1
                    st.append(-v)
                    for u in adj[v]:
                        st.append(u)

        seen = [0] * (N + 1)
        num = 0
        for v0 in reversed(order):
            if seen[v0]:
                continue
            num += 1
            st = deque()
            st.append(v0)
            seen[v0] = 1
            compressed[v0] = num
            while st:
                v = st.pop()
                for u in adj_rev[v]:
                    if seen[u]:
                        continue
                    seen[u] = 1
                    compressed[u] = num
                    st.append(u)

        return num, compressed

    # 縮約後のグラフを構築
    # 先にSCC()を実行してnum, compressedを作っておく
    def construct(adj, num, compressed):
        N = len(adj) - 1
        adj_compressed = [set() for _ in range(num + 1)]
        for v in range(1, N + 1):
            v_cmp = compressed[v]
            for u in adj[v]:
                u_cmp = compressed[u]
                if v_cmp != u_cmp:
                    adj_compressed[v_cmp].add(u_cmp)
        return adj_compressed

    class TwoSat:
        def __init__(self, N):
            self.N = N
            self.adj = [[] for _ in range(2 * N + 1)]
            self.adj_rev = [[] for _ in range(2 * N + 1)]
            self.compressed = None

        # (a == a_bool) or (b = b_bool)というクローズを追加
        # a, b は1-indexed
        def add_clause(self, a, a_bool, b, b_bool):
            if not a_bool:
                a += self.N
            if not b_bool:
                b += self.N
            if a <= self.N:
                self.adj[a + self.N].append(b)
                self.adj_rev[b].append(a + self.N)
            else:
                self.adj[a - self.N].append(b)
                self.adj_rev[b].append(a - self.N)
            if b <= self.N:
                self.adj[b + self.N].append(a)
                self.adj_rev[a].append(b + self.N)
            else:
                self.adj[b - self.N].append(a)
                self.adj_rev[a].append(b - self.N)

        def satisfiable(self):
            _, self.compressed = SCC(self.adj, self.adj_rev)
            for i in range(1, self.N + 1):
                if self.compressed[i] == self.compressed[i + self.N]:
                    return False
            return True

        # 直前に読んだsatisfiableの割り当てを返す
        # 長さN+1のbool値の配列を返す
        def answer(self):
            assert self.compressed is not None
            ret = [True] * (self.N + 1)
            for i in range(1, self.N + 1):
                if self.compressed[i] < self.compressed[i + self.N]:
                    ret[i] = False
            return ret

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

    TS = TwoSat(N)
    for i in range(N):
        for j in range(i+1, N):
            if abs(X[i] - X[j]) < D:
                TS.add_clause(i+1, 0, j+1, 0)
            if abs(X[i] - Y[j]) < D:
                TS.add_clause(i+1, 0, j+1, 1)
            if abs(Y[i] - X[j]) < D:
                TS.add_clause(i+1, 1, j+1, 0)
            if abs(Y[i] - Y[j]) < D:
                TS.add_clause(i+1, 1, j+1, 1)
    ok = TS.satisfiable()
    if not ok:
        print("No")
    else:
        print("Yes")
        ans = TS.answer()
        for i in range(N):
            if ans[i+1]:
                print(X[i])
            else:
                print(Y[i])


if __name__ == '__main__':
    main()