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:
#-------最強ライブラリ2-SAT(Python)------
#最強ライブラリSCC(Python)が必要

class two_sat:
  def __init__(s):
    s._n = 0
    s.scc = scc_graph(0)
  def __init__(s, n):
    s._n = n
    s._answer = [False] * n
    s.scc = scc_graph(2 * n)

  # クローズを足す
  # クローズってなに
  def add_clause(s, i, f, j, g):
    s.scc.add_edge(2 * i + (not f), 2 * j + (g))
    s.scc.add_edge(2 * j + (not g), 2 * i + (f))
  
  # 判定
  # O(n + m)
  def satisfiable(s):
    id = s.scc.scc_ids()[1]
    for i in range(s._n):
      if id[2 * i] == id[2 * i + 1]: return False
      s._answer[i] = id[2 * i] < id[2 * i + 1]
    return True

  # クローズを満たす割当を返す
  # satisfiableがTrueとなった後に呼ばないと意味ない
  # O(1だよね？）
  def answer(s): return s._answer


#-------最強ライブラリここまで------


#-------最強ライブラリSCC(Python)ver25252------

import copy
import sys
sys.setrecursionlimit(1000000)
 
class csr:
  # start 頂点iまでの頂点が、矢元として現れた回数
  # elist 矢先のリストを矢元の昇順にしたもの
  def __init__(s, n, edges):
    s.start = [0] * (n + 1)
    s.elist = [[] for _ in range(len(edges))]
    for e in edges:
      s.start[e[0] + 1] += 1
    for i in range(1, n + 1):
      s.start[i] += s.start[i - 1]
    counter = copy.deepcopy(s.start)
    for e in edges:
      s.elist[counter[e[0]]] = e[1]
      counter[e[0]] += 1
 
class scc_graph:
 
  edges = []
 
  # n 頂点数
  def __init__(s, n): s._n = n
  def num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  def add_edge(s, frm, to): s.edges.append([frm, [to]])
 
  # グループの個数と各頂点のグループidを返す
  def scc_ids(s):
    g = csr(s._n, s.edges)
    now_ord = group_num = 0
    visited = []
    low = [0] * s._n
    ord = [-1] * s._n
    ids = [0] * s._n
    # 再帰関数 
    def dfs(self, v, now_ord, group_num):
      low[v] = ord[v] = now_ord
      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:
          now_ord, group_num = self(self, to, now_ord, group_num)
          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] = s._n
          ids[u] = group_num
          if u == v: break
        group_num += 1
      return now_ord, group_num
 
    for i in range(s._n):
      if ord[i] == -1: now_ord, group_num = dfs(dfs, i, now_ord, group_num)
    for i in range(s._n):
      ids[i] = group_num - 1 - ids[i]
    return [group_num, ids]
 
  # 強連結成分となっている頂点のリストのリスト トポロジカルソート済み
  # O(n + m)
  def scc(s):
    ids = s.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(s._n):
      groups[ids[1][i]].append(i)
    return groups
 
 
#-------最強ライブラリここまで------

def main():
  input = sys.stdin.readline

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

  ts = two_sat(N)

  for i in range(N):
    for j in range(i + 1, N):
      xi, yi = XY[i]
      xj, yj = XY[j]
      # 距離がD未満の組み合わせに関して、
      # 少なくとも一つは使用しない
      # → 少なくとも一つは別の座標を使用する
      # というルールを追加する
      if (abs(xi - xj) < D):
        ts.add_clause(i, False, j, False)
      if (abs(xi - yj) < D):
        ts.add_clause(i, False, j, True)
      if (abs(yi - xj) < D):
        ts.add_clause(i, True, j, False)
      if (abs(yi - yj) < D):
        ts.add_clause(i, True, j, True)

  if not ts.satisfiable():
    print("No")
    exit()

  print("Yes")
  answer = ts.answer()
  for i in range(N):
    x, y = XY[i]
    if answer[i]:
      print(x)
    else:
      print(y)

main()