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;

struct Strongly_Connected_Component {
  int n, k;
  vector<vector<int>> G, reverseG;
  vector<int> vs, cmp;
  vector<bool> used;
  Strongly_Connected_Component(int newv = 1) {
    n = newv;
    G.resize(n);
    reverseG.resize(n);
    used.resize(n, 0);
    cmp.resize(n);
  }

  bool add(int from, int to) {
    G[from].push_back(to);
    reverseG[to].push_back(from);
    return 1;
  }
  void dfs(int v) {
    used[v] = true;
    for (auto to : G[v])
      if (!used[to]) dfs(to);
    vs.push_back(v);
  }
  void rdfs(int v) {
    used[v] = true;
    cmp[v] = k;
    for (auto to : reverseG[v])
      if (!used[to]) rdfs(to);
  }
  int solve() {
    used.assign(n, 0);
    vs.clear();
    for (int v = 0; v < n; ++v)
      if (!used[v]) dfs(v);
    used.assign(n, 0);
    k = 0;
    for (int i = (int)vs.size() - 1; i >= 0; --i)
      if (!used[vs[i]]) {
        rdfs(vs[i]);
        ++k;
      }
    return k;
  }
  vector<vector<int>> make_graph(bool dosolve = 1) {
    if (dosolve) solve();
    vector<vector<int>> res(k);
    for (int i = 0; i < n; ++i)
      for (int to : G[i])
        if (!issame(i, to)) res[cmp[i]].push_back(cmp[to]);
    for (auto& v : res) {
      sort(v.begin(), v.end());
      v.erase(unique(v.begin(), v.end()), v.end());
    }
    return res;
  }
  vector<vector<int>> make_list(bool dosolve = 1) {
    if (dosolve) solve();
    vector<vector<int>> res(k);
    for (int i = 0; i < n; ++i) res[cmp[i]].push_back(i);
    return res;
  }
  bool issame(int l, int r) { return cmp[l] == cmp[r]; }
};

struct Two_SAT {
  int n;
  Strongly_Connected_Component scc;
  Two_SAT(int _n = 1) : n(_n), scc(2 * _n) {}
  // a v c : !a -> c && !c -> a
  void add(int a, bool b, int c, bool d) {
    scc.add(a + b * n, c + (!d) * n);
    scc.add(c + d * n, a + (!b) * n);
  }
  bool solve() {
    scc.solve();
    for (int i = 0; i < n; ++i)
      if (scc.cmp[i] == scc.cmp[i + n]) return 0;
    return 1;
  }
  vector<bool> make_vec() {
    vector<bool> res;
    if (!solve()) return res;
    res.assign(n, 0);
    for (int i = 0; i < n; ++i) res[i] = scc.cmp[i] > scc.cmp[i + n];
    return res;
  }
};

int main() {
  int n, d;
  cin >> n >> d;
  Two_SAT ts(2 * n);
  using P = pair<int, int>;
  vector<P> v(n);
  for (int i = 0; i < n; ++i) ts.add(i, 1, i + n, 1);
  for (auto& p : v) cin >> p.first >> p.second;
  for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j) {
      if (abs(v[i].first - v[j].first) < d) ts.add(i, 0, j, 0);
      if (abs(v[i].first - v[j].second) < d) ts.add(i, 0, j + n, 0);
      if (abs(v[i].second - v[j].first) < d) ts.add(i + n, 0, j, 0);
      if (abs(v[i].second - v[j].second) < d) ts.add(i + n, 0, j + n, 0);
    }
  auto res = ts.make_vec();
  if (res.size()) {
    cout << "Yes" << endl;
    for (int i = 0; i < n; ++i)
      cout << (res[i] ? v[i].first : v[i].second) << endl;
  } else
    cout << "No" << endl;
  return 0;
}