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:
import sys
sys.setrecursionlimit(10**9)
def SCC(G):
  D=[]
  C=[len(G)-1]
  U=[1]*len(G)
  def DFS(x):
    if U[x]:
      U[x]=0
      for i in range(len(G[x])):
        DFS(G[x][i])
      D.append(x)
  
  for i in range(len(G)):
    if U[i]:
      DFS(i)
  GR=[[] for i in range(len(G))]
  for i in range(len(G)):
    for j in range(len(G[i])):
      GR[G[i][j]].append(i)
  R=[]
  U=[1]*len(G)
  def DFSR(x):
    if U[x]:
      R[-1].append(x)
      U[x]=0
      for i in range(len(GR[x])):
        DFSR(GR[x][i])
  
  for i in range(len(G)-1,-1,-1):
    if U[D[i]]:
      R.append([])
      DFSR(D[i])
  return R

N,D=map(int,input().split())
G=[[] for i in range(2*N)]
X=[list(map(int,input().split())) for i in range(N)]
for i in range(N):
  for j in range(i+1,N):
    for k in range(2):
      for l in range(2):
        if abs(X[i][k]-X[j][l])<D:
          G[k*N+i].append((l^1)*N+j)
          G[l*N+j].append((k^1)*N+i)
G=SCC(G)
C=[0]*(2*N)
for i in range(len(G)):
  for j in range(len(G[i])):
    C[G[i][j]]=i
for i in range(N):
  if C[i]==C[i+N]:
    print('No')
    exit()
print('Yes')
for i in range(N):
  if C[i]>C[i+N]:
    print(X[i][0])
  else:
    print(X[i][1])