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 <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;
#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;

using namespace std;
typedef long long ll;

const int N_MAX = 200000;
int N;
bool used[N_MAX];
int idx[N_MAX];
vector<int> vs;
vector<int> buf;
vector<int> G[N_MAX];
vector<int> G_inv[N_MAX];
vector<vector<int>> ans;

void clear(){
    for(int i = 0; i < N; i++) used[i] = false;
}

void dfs1(int v){
    used[v] = true;
    for(int i = 0; i < G[v].size(); i++){
        if(!used[G[v][i]]) dfs1(G[v][i]);
    }
    vs.push_back(v);
}

void dfs2(int v, int k){
    used[v] = true;
    idx[v] = k;
    for(int i = 0; i < G_inv[v].size(); i++){
        if(!used[G_inv[v][i]]) dfs2(G_inv[v][i], k);
    }
    buf.push_back(v);
}

void scc(){
    for(int i = 0; i < N; i++){
        if(!used[i]) dfs1(i);
    }
    clear();
    int cur = 0;
    for(int i = vs.size()-1; i >= 0; i--){
        if(!used[vs[i]]) {
            dfs2(vs[i], cur);
            cur++;
            ans.push_back(buf);
            buf.clear();
        }
    }
}

ll X[1000], Y[1000];
ll D;

int scc_idx[2000];


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    int n; cin >> n >> D;
    N = 2*n;
    for(int i = 0; i < n; i++) cin >> X[i] >> Y[i];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(i == j) continue;
            ll d1 = abs(X[i]-X[j]);
            ll d2 = abs(X[i]-Y[j]);
            
            if(d1 < D && d2 < D) {
                G[i].push_back(n+i);
                G_inv[n+i].push_back(i);
            }else if(d1 < D){
                G[i].push_back(j+n);
                G_inv[j+n].push_back(i);
            }else if(d2 < D){
                G[i].push_back(j);
                G_inv[j].push_back(i);
            }

            ll d3 = abs(Y[i]-X[j]);
            ll d4 = abs(Y[i]-Y[j]);
            if(d3 < D && d4 < D) {
                G[n+i].push_back(i);
                G_inv[i].push_back(n+i);
            }else if(d3 < D){
                G[n+i].push_back(j+n);
                G_inv[j+n].push_back(n+i);
            }else if(d4 < D){
                G[n+i].push_back(j);
                G_inv[j].push_back(n+i);
            }
        }
    }
    scc();
    for(int idx = 0; idx < ans.size(); idx++){
        for(int i : ans[idx]){
            scc_idx[i] = idx;
        }
    }
    for(int i = 0; i < n; i++){
        if(scc_idx[i] == scc_idx[i+n]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    for(int i = 0; i < n; i++){
        if(scc_idx[i] < scc_idx[i+n]){
            cout << Y[i] << endl;
        }else{
            cout << X[i] << endl;
        }
    }
}