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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<int,int> P;

struct StronglyConnectedComponent{
  int n, comp_size;
  vector<vector<int>> g, revg;
  vector<int> comp, order, used;

  StronglyConnectedComponent (int sz) {
    n = sz;
    g.resize(n); revg.resize(n);
    comp.assign(n, -1);
    used.assign(n, 0);
  }

  int operator[] (int u) {
    return comp[u];
  }

  void add (int u, int v){
    g[u].emplace_back(v);
    revg[v].emplace_back(u);
  }

  void dfs (int u){
    if (used[u]) return ;
    used[u] = 1;
    for (auto v : g[u]) dfs(v);
    order.emplace_back(u);
    return ;
  }

  void rdfs (int u, int k){
    if (comp[u] != -1) return ;
    comp[u] = k;
    for (auto v : revg[u]) rdfs(v, k);
    return ;
  }

  void build (vector<vector<int>> &ref){
    for (int i = 0; i < n; i++) dfs(i);
    reverse(order.begin(), order.end());
    int cur = 0;
    for (auto i : order) {
      if (comp[i] == -1) {
        rdfs(i, cur);
        cur++;
      }
    }
    ref.resize(cur);
    for (int i = 0; i < g.size(); i++) {
      for (auto j : g[i]) {
        int u = comp[i], v = comp[j];
        if (u == v) continue;
        ref[u].emplace_back(v);
      }
    }
  }

};

int main(){

  int n, d;
  cin >> n >> d;
  StronglyConnectedComponent scc(2 * n);
  vector<int> x(n), y(n);
  rep(i,n) cin >> x[i] >> y[i];

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      //　x : 1, y : 0
      if (i == j) continue;
      if (abs(x[i] - x[j]) < d) scc.add(i, j + n);
      if (abs(y[i] - x[j]) < d) scc.add(i + n, j + n);
      if (abs(x[i] - y[j]) < d) scc.add(i, j);
      if (abs(y[i] - y[j]) < d) scc.add(i + n, j);
    }
  }

  vector<vector<int>> g;
  scc.build(g);
  for (int i = 0; i < n; i++) {
    if (scc[i] == scc[i + n]) {
      cout << "No" << endl;
      return 0;
    } 
  }
  cout << "Yes" << endl;
  for (int i = 0; i < n; i++) cout << (scc[i] > scc[i + n] ? x[i] : y[i]) << endl;

  return 0;
}