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 StronglyConnectedComponents{
    vector<vector<int>> G,rG,C,T;
    vector<int> vs,cmp,used;
    StronglyConnectedComponents(int n):G(n),rG(n),cmp(n),used(n){}
    void add_edge(int u,int v){
        G[u].emplace_back(v);
        rG[v].emplace_back(u);
    }
    void dfs(int v){
        used[v]=1;
        for (int u:G[v]) if(!used[u]) dfs(u);
        vs.emplace_back(v);
    }
    void rdfs(int v,int k){
        used[v]=1;
        cmp[v]=k;
        C[k].emplace_back(v);
        for (int u:rG[v]) if (!used[u]) rdfs(u,k);
    }
    int build(){
        int n=G.size();
        for (int i=0;i<n;++i) if (!used[i]) dfs(i);
        fill(used.begin(),used.end(),0);
        int k=0;
        for (int i=n-1;i>=0;--i){
            if (!used[vs[i]]){
                C.emplace_back(),T.emplace_back();
                rdfs(vs[i],k++);
            }
        }
        for (int v=0;v<n;++v) for (int u:G[v]){
            if (cmp[v]!=cmp[u]) T[cmp[v]].emplace_back(cmp[u]);
        }
        for (int i=0;i<k;++i){
            sort(T[i].begin(),T[i].end());
            T[i].erase(unique(T[i].begin(),T[i].end()),T[i].end());
        }
        return k;
    }
    int operator[](int i) const{
        return cmp[i];
    }
};

struct TwoSatisfiability{
    int n;
    StronglyConnectedComponents SCC;
    TwoSatisfiability(int n):n(n),SCC(n*2){}
    int neg(int v){return (n+v)%(n*2);}
    void add_if(int u,int v){
        SCC.add_edge(u,v);
        SCC.add_edge(neg(v),neg(u));
    }
    void add_or(int u,int v){
        add_if(neg(u),v);
    }
    void add_nand(int u,int v){
        add_if(u,neg(v));
    }
    void set_true(int v){
        SCC.add_edge(neg(v),v);
    }
    void set_false(int v){
        SCC.add_edge(v,neg(v));
    }
    vector<int> build(){
        SCC.build();
        vector<int> res(n);
        for (int i=0;i<n;++i){
            if (SCC[i]==SCC[n+i]) return {};
            res[i]=SCC[i]>SCC[n+i];
        }
        return res;
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,D; cin >> N >> D;
    vector<int> X(N),Y(N);
    for (int i=0;i<N;++i) cin >> X[i] >> Y[i];
    TwoSatisfiability TS(2*N);
    for (int i=0;i<2*N;i+=2){
        TS.add_or(i,i+1);
        TS.add_nand(i,i+1);
    }
    for (int i=0;i<N;++i){
        for (int j=i+1;j<N;++j){
            if (abs(X[i]-X[j])<D) TS.add_nand(i<<1|0,j<<1|0);
            if (abs(X[i]-Y[j])<D) TS.add_nand(i<<1|0,j<<1|1);
            if (abs(Y[i]-X[j])<D) TS.add_nand(i<<1|1,j<<1|0);
            if (abs(Y[i]-Y[j])<D) TS.add_nand(i<<1|1,j<<1|1);
        }
    }

    vector<int> ans=TS.build();
    if (ans.empty()){cout << "No" << '\n'; return 0;}
    cout << "Yes" << '\n';
    for (int i=0;i<N;++i){
        cout << (ans[i<<1|0]?X[i]:Y[i]) << '\n';
    }
}