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:
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

void stronglyConnectedComponents(
    const vector<vector<int> >& edges, vector<int>& indexConvert,
    vector<vector<int> >& nodesOut)
{
    const int n = edges.size();
    vector<int> num(n, -1), low(n, -1);
    vector<bool> isStk(n, false);
    stack<int> stk;
    int cnt = -1;
    nodesOut.clear();

    for(int i=0; i<n; ++i){
        stack<pair<int, unsigned> > arg;
        arg.push(make_pair(i, 0));

        while(!arg.empty()){
            int v = arg.top().first;
            unsigned j = arg.top().second;
            arg.pop();

            if(j == 0){
                if(num[v] != -1)
                    continue;
                num[v] = low[v] = ++ cnt;
                stk.push(v);
                isStk[v] = true;
            }
            else{
                int w = edges[v][j-1];
                if(isStk[w])
                    low[v] = min(low[v], low[w]);
            }

            if(j < edges[v].size()){
                arg.push(make_pair(v, j + 1));
                int w = edges[v][j];
                arg.push(make_pair(w, 0));
            }
            else if(low[v] == num[v]){
                nodesOut.push_back(vector<int>());
                for(;;){
                    int w = stk.top();
                    stk.pop();
                    isStk[w] = false;
                    nodesOut.back().push_back(w);
                    if(v == w)
                        break;
                }
            }
        }
    }

    reverse(nodesOut.begin(), nodesOut.end()); // DAGにするために反転させる
    const int m = nodesOut.size();
    indexConvert.resize(n);
    for(int i=0; i<m; ++i){
        for(unsigned j=0; j<nodesOut[i].size(); ++j)
            indexConvert[nodesOut[i][j]] = i;
    }
}

bool is2sat(int n, const vector<pair<int, bool> >& v, vector<bool>& ans)
{
    vector<vector<int> > edges(2*n);
    for(unsigned i=0; i<v.size(); i+=2){
        int a = v[i].first * 2 + (v[i].second ? 0 : 1);
        int b = v[i+1].first * 2 + (v[i+1].second ? 0 : 1);
        edges[a^1].push_back(b);
        edges[b^1].push_back(a);
    }

    vector<int> indexConvert;
    vector<vector<int> > nodes;
    stronglyConnectedComponents(edges, indexConvert, nodes);

    ans.resize(n);
    for(int i=0; i<n; ++i){
        if(indexConvert[2*i] < indexConvert[2*i+1])
            ans[i] = false;
        else if(indexConvert[2*i+1] < indexConvert[2*i])
            ans[i] = true;
        else
            return false;
    }
    return true;
}

int main()
{
    int n, d;
    cin >> n >> d;
    vector<int> x(2*n);
    for(int i=0; i<2*n; ++i)
        cin >> x[i];

    vector<pair<int, bool> > v;
    for(int i=0; i<2*n; ++i){
        for(int j=i+1; j<2*n; ++j){
            if(abs(x[i] - x[j]) < d){
                v.push_back(make_pair(i / 2, i % 2 != 0));
                v.push_back(make_pair(j / 2, j % 2 != 0));
            }
        }
    }

    vector<bool> ans;
    if(is2sat(n, v, ans)){
        cout << "Yes" << endl;
        for(int i=0; i<n; ++i){
            if(ans[i])
                cout << x[2*i] << endl;
            else
                cout << x[2*i+1] << endl;
        }
    }
    else{
        cout << "No" << endl;
    }

    return 0;
}