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;
using ll = long long;

struct SCC {
public:
    SCC(vector<vector<int>>& G) : G(G), comp(G.size(), -1), visited(G.size()), G_rev(G.size()) {
        for (int u = 0; u < G.size(); u++) {
            for (int v : G[u]) G_rev[v].push_back(u);
        }

        for (int v = 0; v < G.size(); v++) dfs(v);
        reverse(order.begin(), order.end());
        int c = 0;
        for (int v : order) if (comp[v] == -1) rdfs(v, c++);
    }

    int operator[](int k) const {
        return comp[k];
    }

private:
    vector<vector<int>> G, G_rev;
    vector<int> comp, order;
    vector<bool> visited;

    void dfs(int u) {
        if (visited[u]) return;
        visited[u] = true;
        for (int v : G[u]) dfs(v);
        order.push_back(u);
    }

    void rdfs(int u, int c) {
        if (comp[u] != -1) return;
        comp[u] = c;
        for (int v : G_rev[u]) rdfs(v, c);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, D;
    cin >> N >> D;
    vector<int> X(N), Y(N);
    for (int i = 0; i < N; i++) cin >> X[i] >> Y[i];
    vector<vector<int>> G(2*N);
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            if (abs(X[i] - X[j]) < D) {
                G[i].push_back(N + j);
                G[j].push_back(N + i);
            }
            if (abs(X[i] - Y[j]) < D) {
                G[i].push_back(j);
                G[N + j].push_back(N + i);
            }
            if (abs(Y[i] - X[j]) < D) {
                G[N + i].push_back(N + j);
                G[j].push_back(i);
            }
            if (abs(Y[i] - Y[j]) < D) {
                G[N + i].push_back(j);
                G[N + j].push_back(i);
            }
        }
    }
    SCC scc(G);
    for (int i = 0; i < N; i++) {
        if (scc[i] == scc[N + i]) {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
    for (int i = 0; i < N; i++) {
        if (scc[i] > scc[N + i]) cout << X[i];
        else cout << Y[i];
        cout << "\n";
    }
}