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>
using namespace std;
struct sat2{
    int N, n;
    vector<vector<int>> G, rG;
    vector<bool> used;
    vector<int> temp;
    vector<int> order;//分解後のトポロジカル順序
    vector<bool> judge;
    sat2(int V){
        G.resize(2 * V);
        rG.resize(2 * V);
        N = 2 * V;
        n = V;
        order.resize(2 * V);
        judge.resize(V);
    }
    void add_edge(int s, int t){
        G[s].push_back(t);
        rG[t].push_back(s);
    }
    void add(int s, bool f, int t, bool g){
        add_edge(s + (f ? n : 0), t + (g ? 0 : n));
        add_edge(t + (g ? n : 0), s + (f ? 0 : n));
    }
    void dfs(int s){
        used[s] = true;
        for(int j: G[s]){
            if(!used[j]) dfs(j);
        }
        temp.push_back(s);
    }
    void rdfs(int s, int k){
        used[s] = true;
        order[s] = k;
        for(int j: rG[s]){
            if(!used[j]) rdfs(j, k);
        }
    }
    bool solve(){//分解後の頂点数を返す
        used.resize(N, false);
        for(int i = 0; i < N; i++){
            if(!used[i]) dfs(i);
        }
        used.assign(N, false);  
        int k = 0;
        for(int i = (int)temp.size() - 1; i >= 0; i--){ //番号が大きい方から順にdfs
            if(!used[temp[i]]) {
                rdfs(temp[i], k);
                k++;
            }
        }
        bool flag = true;
        for(int i = 0; i < n; i++){
            if(order[i] > order[i + n]) judge[i] = true;
            else if(order[i] < order[i + n]) judge[i] = false;
            else flag = false;
        }
        return flag;
    }
};
int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int N, D;
    cin >> N >> D;
    sat2 sat2(N);
    vector<int> X(N), Y(N);
    for(int i = 0; i < N; i++) cin >> X[i] >> Y[i];
    for(int i = 0; i < N; i++){
        for(int j = i + 1; j < N; j++){
            if(abs(X[i] - X[j]) < D) sat2.add(i, false, j, false);
            if(abs(X[i] - Y[j]) < D) sat2.add(i, false, j, true);
            if(abs(Y[i] - X[j]) < D) sat2.add(i, true, j, false);
            if(abs(Y[i] - Y[j]) < D) sat2.add(i, true, j, true);
        }
    }
    bool flag = sat2.solve();
    if(!flag) cout << "No" << endl;
    else{
        cout << "Yes" << endl;
        for(int i = 0; i < N; i++){
            if(sat2.judge[i]) cout << X[i] << endl;
            else cout << Y[i] << endl;
        }
    }
}