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 <iostream>
#include <vector>
#include <map>
using namespace std;

struct SCC      //StronglyConnectedComponents
{
    int n;
    int k;
    vector<vector<int>> g, rg;
    vector<bool> used;
    vector<int> cmp;
    vector<int> vs;
    
    void add_edge(int from, int to){
        g[from].push_back(to);
        rg[to].push_back(from);
    }
    
    SCC(){}
    
    SCC(int n) : n(n){
        g.resize(n);
        rg.resize(n);
        used.resize(n);
        cmp.resize(n);
        vs.resize(n);
    }
    
    void dfs(int u, int &l){
        used[u] = true;
        for(int v : g[u]){
            if(!used[v]) dfs(v, l);
        }
        vs[l] = u;
        l++;
    }
    
    void rdfs(int u, int k){
        used[u] = true;
        cmp[u] = k;
        for(int v : rg[u]){
            if(!used[v]) rdfs(v, k);
        }
    }
    
    int decomposition(){
        int l = 0;
        for(int i = 0; i < n; i++){
            if(!used[i]) dfs(i, l);
        }
        fill(used.begin(), used.end(), false);
        k = 0;
        for(int i = n - 1; i >= 0; i--){
            if(!used[vs[i]]){
                rdfs(vs[i], k);
                k++;
            }
        }
        return k;
    }
};

struct TwoSAT
{
    int n;
    SCC g;
    vector<bool> f;
    
    TwoSAT(int n) : n(n){
        g.n = n * 2;
        g.g.resize(n * 2);
        g.rg.resize(n * 2);
        g.used.resize(n * 2);
        g.cmp.resize(n * 2);
        g.vs.resize(n * 2);
        f.resize(n);
    }
    
    void add_edge(int a, bool fa, int b, bool fb){
        g.add_edge(a + int(!fa) * n, b + int(fb) * n);
        g.add_edge(b + int(!fb) * n, a + int(fa) * n);
    }
    
    bool judge(){
        g.decomposition();
        for(int i = 0; i < n; i++){
            if(g.cmp[i] == g.cmp[i + n]) return false;
            if(g.cmp[i] > g.cmp[i + n]) f[i] = false;
            else f[i] = true;
        }
        return true;
    }
};

int main()
{
    int n, d;
    cin >> n >> d;
    int x[1005], y[1005];   // x : false, y : true
    for(int i = 0; i < n; i++) cin >> x[i] >> y[i];
    TwoSAT sat(n);
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(abs(x[i] - x[j]) < d) sat.add_edge(i, true, j, true);
            if(abs(x[i] - y[j]) < d) sat.add_edge(i, true, j, false);
            if(abs(y[i] - x[j]) < d) sat.add_edge(i, false, j, true);
            if(abs(y[i] - y[j]) < d) sat.add_edge(i, false, j, false);
        }
    }
    if(!sat.judge()){
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    for(int i = 0; i < n; i++){
        if(!sat.f[i]) cout << x[i] << endl;
        else cout << y[i] << endl;
    }
}