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>
//#include <chrono>
#pragma GCC optimize("Ofast")
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
typedef pair<ll, ll> P;
const ll INF = (1LL<<60);

void dfs1(int n, mat &G, vec &ord){
    int k(0);
    vector<int> iter(n, -1);
    stack<int> sta;
    rep(i, n) {
        if(iter[i] < 0) sta.push(i);
        while (!sta.empty()) {
            int v = sta.top();
            if ((++iter[v]) == G[v].size()) {
                ord[k++] = v;
                sta.pop();
            } else {
                int to = G[v][iter[v]];
                if(iter[to] < 0) sta.push(to);
            }
        }
    }
}
void dfs2(int n, mat &G, vec &ord, mat &res){
    int k(0);
    vector<bool> used(n, false);
    stack<int> sta;
    Rrep(i, n){
        int s = ord[i];
        if(!used[s]){
            used[s] = true;
            sta.push(s);
            while(!sta.empty()){
                int v = sta.top(); sta.pop();
                res[k].push_back(v);
                for(int to : G[v]) {
                    if(!used[to]) {
                        used[to] = true;
                        sta.push(to);
                    }
                }
            }
            ++k;
        }
    }
    res.resize(k);
}

void scc(mat &G, mat &res){
    int n = G.size();
    res.resize(n);
    mat G_rev(n, vec(0));
    rep(u, n) for(int v : G[u]) G_rev[v].push_back(u);
    vec ord(n);
    dfs1(n, G, ord);
    dfs2(n, G_rev, ord, res);
}

int main() {
    cin >> N >> K;
    mat G(N * 2, vec(0)), scc_list;
    vec x(N * 2), pos(N * 2);
    rep(i, N) cin>>x[i]>>x[i + N];
    rep(i, N * 2){
        rep(j, i) {
            if(abs(x[i] - x[j]) < K) {
                int i_inv = (i + N) % (N * 2), j_inv = (j + N) % (N * 2);
                G[i].push_back(j_inv);
                G[j].push_back(i_inv);
            }
        }
    }
    scc(G, scc_list);
    rep(i, (int)scc_list.size()){
        for(int v : scc_list[i]) pos[v] = i;
    }
    //rep(i, N) cout<<pos[i]<<' '<<pos[i + N]<<endl;
    bool ok = true;
    rep(i, N) if(pos[i] == pos[i + N]) ok = false;
    cout<<(ok ? "Yes" : "No")<<endl;
    if(ok){
        rep(i, N){
            cout<<(pos[i] > pos[i + N] ? x[i] : x[i + N])<<endl;
        }
    }
}