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:
# Date [ 2020-09-12 10:24:21 ]
# Problem [ h.py ]
# Author Koki_tkg

class two_sat:
    def __init__(self, n: int):
        self._n = n
        self.scc = scc_graph(2 * n)
        self._answer = [False] * n
    
    def add_clause(self, i: int, f: bool, j: int, g: bool):
        assert 0 <= i and i < self._n
        assert 0 <= j and 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) -> bool:
        _id = self.scc.scc_ids()[1]
        for i in range(self._n):
            if _id[2 * i] == _id[2 * i + 1]: return False
            self._answer[i] = _id[2 * i] < _id[2 * i + 1]
        return True
    
    def answer(self): return self._answer

class csr:
    def __init__(self, n: int, edges: list):
        from copy import deepcopy
        self.start = [0] * (n + 1)
        self.elist = [[] for _ in range(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 = deepcopy(self.start)
        for e in edges:
            self.elist[counter[e[0]]] = e[1]; counter[e[0]] += 1

class scc_graph:
    # private
    edges = []
    
    # public
    def __init__(self, n: int):
        self._n = n
        self.now_ord = 0; self.group_num = 0
    
    def num_vertices(self): return self._n

    def add_edge(self, _from: int, _to: int): self.edges.append((_from, [_to]))
    
    def scc_ids(self):
        g = csr(self._n, self.edges)
        visited = []; low = [0] * self._n; ord = [-1] * self._n; ids = [0] * self._n
        
        def dfs(s, v: int):
            low[v] = ord[v] = self.now_ord; self.now_ord += 1
            visited.append(v)
            for i in range(g.start[v], g.start[v + 1]):
                to = g.elist[i][0]
                if ord[to] == -1:
                    s(s, to)
                    low[v] = min(low[v], low[to])
                else:
                    low[v] = min(low[v], ord[to])
            if low[v] == ord[v]:
                while True:
                    u = visited.pop()
                    ord[u] = self._n
                    ids[u] = self.group_num
                    if u == v: break
                self.group_num += 1

        for i in range(self._n):
            if ord[i] == -1: dfs(dfs, i)
        for i in range(self._n):
            ids[i] = self.group_num - 1 - ids[i]

        return (self.group_num, ids)
        
    def scc(self):
        ids = self.scc_ids()
        group_num = ids[0]
        counts = [0] * group_num
        for x in ids[1]: counts[x] += 1
        groups = [[] for _ in range(group_num)]
        for i in range(self._n):
            groups[ids[1][i]].append(i)
        return groups


import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n, d = read_ints()
    xy = [read_int_list() for _ in range(n)]
    tw = two_sat(n)
    
    for i in range(n):
        for j in range(i + 1, n):
            for x in range(2):
                if abs(xy[i][0] - xy[j][0]) < d: tw.add_clause(i, False, j, False)
                if abs(xy[i][0] - xy[j][1]) < d: tw.add_clause(i, False, j, True)
                if abs(xy[i][1] - xy[j][0]) < d: tw.add_clause(i, True, j, False)
                if abs(xy[i][1] - xy[j][1]) < d: tw.add_clause(i, True, j, True)
                
    if not tw.satisfiable():
        print('No')
        exit()
    print('Yes')
    ans = tw.answer()
    for i, flag in enumerate(ans):
        print(xy[i][0] if flag else xy[i][1])

if __name__ == '__main__':
    Main()