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>
#define rep(i,n) for (int i = 0; i < (int)(n); i ++)
#define irep(i,n) for (int i = (int)(n) - 1;i >= 0;--i)
using namespace std;
using ll = long long;
using PL = pair<ll,ll>;
using P = pair<int,int>;
constexpr int INF = 1000000000;
constexpr long long HINF = 1000000000000000;
constexpr long long MOD = 1000000007;// = 998244353;
constexpr double EPS = 1e-4;
constexpr double PI = 3.14159265358979;


struct StronglyConnectedComponents {
    int N;
    vector<vector<int>> G,rG;
    vector<int> group,order;

    StronglyConnectedComponents(int _N): N(_N) {
        G.resize(N); rG.resize(N); group.assign(N,1);
    }
    
    void add_edge(int a,int b) {
        G[a].push_back(b);
        rG[b].push_back(a);
    }

    void dfs(int v) {
        group[v] = -1;
        for (int e: G[v]) {
            if (group[e] > 0) dfs(e);
        }
        order.push_back(v);
    }

    void rdfs(int v,int cnt) {
        group[v] = cnt;
        for (int e: rG[v]) {
            if (group[e] < 0) rdfs(e,cnt);
        }
    }

    void build() {
        for (int i = 0;i < N;i ++) {
            if (group[i] > 0) dfs(i);
        }
        reverse(begin(order),end(order));
        int cnt = 0;
        for (int v: order) {
            if (group[v] < 0) rdfs(v,cnt),cnt++;
        }
    }

    int operator[](int i) {
        return group[i];
    }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int N; ll D; cin >> N >> D;
    vector<ll> X(N),Y(N);
    rep(i,N) cin >> X[i] >> Y[i];

    StronglyConnectedComponents scc(2*N);
    rep(i,N) {
        for (int j = i + 1;j < N;++j) {
            if (abs(X[i] - X[j]) < D) {
                scc.add_edge(i,j + N);
                scc.add_edge(j,i + N);
            }
            if (abs(X[i] - Y[j]) < D) {
                scc.add_edge(i,j);
                scc.add_edge(j + N,i + N);
            }
            if (abs(Y[i] - X[j]) < D) {
                scc.add_edge(i + N,j + N);
                scc.add_edge(j,i);
            }
            if (abs(Y[i] - Y[j]) < D) {
                scc.add_edge(i + N,j);
                scc.add_edge(j + N,i);
            }
        }
    }
    scc.build();
    vector<int> ans(N);
    rep(i,N) {
        if (scc[i] == scc[i + N]) {
            cout << "No" << '\n';
            return 0;
        }
        if (scc[i] < scc[i + N]) ans[i] = Y[i];
        else ans[i] = X[i];
    }
    cout << "Yes" << '\n';
    rep(i,N) cout << ans[i] << '\n';
    return 0;
}