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 SCC{
    int N;
    vector<bool> used;
    vector<int> vs;
    vector<int> cmp;

    void dfs(int v, const vector<vector<int>>& G){
        used[v] = true;
        for(auto u : G[v]){
            if(!used[u]) dfs(u, G);
        }
        vs.push_back(v);
    }

    void rdfs(int v, int k, const vector<vector<int>>& rG){
        used[v] = true;
        cmp[v] = k;
        for(auto u : rG[v]){
            if(!used[u]) rdfs(u, k, rG);
        }
    }

    SCC(int N, const vector<vector<int>>& G):N(N){
        vector<vector<int>> rG(N);
        for(int i=0; i<N; i++) for(int j : G[i]) rG[j].push_back(i);
        used.resize(N);
        fill(used.begin(), used.end(), false);
        for(int v=0; v<N; v++){
            if(!used[v]) dfs(v, G);
        }

        fill(used.begin(), used.end(), false);
        cmp.resize(N);
        int k = 0;
        for(int i = vs.size()-1; i>=0; i--){
            if(!used[vs[i]]) rdfs(vs[i], k++, rG);
        }
    }

    vector<vector<int>> dump_graph(const vector<vector<int>>& G){
        int sz = *max_element(cmp.begin(), cmp.end()) + 1;
        vector<vector<int>> edges2(sz);
        for(int i=0; i<N; i++){
            for(auto j : G[i]){
                if(cmp[i] != cmp[j]){
                    edges2[cmp[i]].push_back(cmp[j]);
                }
            }
        }
        return edges2;
    }
};

int main(){
    int N, D;
    cin >> N >> D;
    vector<int> A(2*N);
    for(int i=0; i<2*N; i++) cin >> A[i];
    vector<vector<int>> edges(2*N);
    for(int i=0; i<2*N; i++) for(int j=0; j<i; j++) if(i/2 != j/2 && abs(A[i] - A[j]) < D){
        edges[i].push_back(j^1);
        edges[j].push_back(i^1);
    }

    SCC scc(2*N, edges);
    
    vector<int> ans(N);
    for(int i=0; i<N; i++){
        int c1 = scc.cmp[2*i], c2 = scc.cmp[2*i+1];
        if(c1 == c2){
            cout << "No" << endl;
            return 0;
        }else if(c1 < c2){
            ans[i] = A[2*i+1];
        }else{
            ans[i] = A[2*i];
        }
    }

    cout << "Yes" << endl;
    for(int a : ans) cout << a << endl;
    return 0;
}