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>
#define F first
#define S second
using namespace std;
typedef long long LL;
struct SCC { int stamp, scc_num;
  struct Node : vector<int> {
    int dfn, low, scc; bool inS;
    Node() { dfn = low = scc = -1; inS = false; }
  };
  vector<Node> N; vector<int> stk;
  void init(int n) {
    N.clear(); N.resize(n); stk.clear();
  }
  void addEdge(int u, int v) { N[u].push_back(v); }
  void Tarjan(int u) { N[u].low = N[u].dfn = stamp++;
    stk.push_back(u); N[u].inS = true;
    for (auto &v : N[u]) if (!~N[v].dfn) Tarjan(v),
      N[u].low = min(N[u].low, N[v].low);
    else if (N[v].inS)
      N[u].low = min(N[u].low, N[v].dfn);
    if (N[u].dfn == N[u].low) {
      int v; do { v = stk.back(); stk.pop_back();
        N[v].scc = scc_num; N[v].inS = false;
      } while (v != u); scc_num++;
    }
  }
  void run() { stamp = scc_num = 0;
    for (int i = 0 ; i < N.size() ; i++)
      if (!~N[i].dfn) Tarjan(i);
  }
};
// LatexBegin
struct _2Sat : SCC {
  void init(int n) { SCC::init(2 * n); }
  /* addCond(0, 0, 1, 1) -> v0 or !v1*/
  void addCond(int o1, int v1, int o2, int v2) {
    addEdge((v1 << 1) | (o1 ^ 1), (v2 << 1) | o2);
    addEdge((v2 << 1) | (o2 ^ 1), (v1 << 1) | o1);
  }
  bool check() {
    for (int i = 0 ; i < N.size() ; i += 2)
      if (N[i].scc == N[i ^ 1].scc) return false;
    return true;
  }
  vector<int> construct() { vector<int> ret;
    for (int i = 0 ; i < N.size() ; i += 2)
      ret.push_back(N[i].scc < N[i ^ 1].scc);
    return assert(check()), ret;
  }
} solver;
// LatexEnd
typedef long long LL;
typedef pair<LL, LL> pii;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; LL d; cin >> n >> d;
    vector<pii> arr(n);
    vector<int> pts;
    for (auto &p : arr) {
        cin >> p.F >> p.S;
        pts.push_back(p.F);
        pts.push_back(p.S);
    }
    solver.init(2 * n);
    for (int i = 0 ; i < 2 * n ; i++) {
        for (int j = 0 ; j < i ; j++) {
            if (abs(pts[i] - pts[j]) >= d)
                continue;
            solver.addEdge(i * 2 + 1, j * 2 + 0);
            solver.addEdge(j * 2 + 1, i * 2 + 0);
        }
    }
    for (int i = 0 ; i < 2 * n ; i += 2) {
        solver.addEdge(i * 2 + 0, (i + 1) * 2 + 1);
        solver.addEdge((i + 1) * 2 + 0, i * 2 + 1);
    }
    solver.run();
    if (solver.check()) {
        cout << "Yes\n";
        auto ans = solver.construct();
        for (int i = 0 ; i < 2 * n ; i += 2) {
            if (ans[i])
                cout << arr[i / 2].S << '\n';
            else
                cout << arr[i / 2].F << '\n';
        }
    } else {
        cout << "No\n";
    }
}