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<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<complex>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
#include <numeric>
using namespace std;
using Complex = complex<double>;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
const double EPS = 1e-10;
double PI = acos(-1.0);
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)

const int MAX_N = 505050;
vector<int>e[MAX_N], er[MAX_N];
int fin[MAX_N], cmp[MAX_N], state[MAX_N];
int cnt = 0;
int num = 0;
void dfs1(int now) {
	state[now] = 1;
	fore(x, e[now]) {
		if (state[x] == 0) {
			cnt++;
			dfs1(x);
		}
	}
	cnt++;
	fin[now] = cnt;
}
void dfs2(int now, int num) {
	state[now] = 1;
	cmp[now] = num;
	fore(x, er[now]) {
		if (state[x] == 0)dfs2(x, num);
	}
}
void scc(int N) {
	//各頂点について終了時間を計算
	for (int i = 0; i < N; i++) {
		if (state[i] == 0)dfs1(i);
	}
	//逆辺を計算
	for (int i = 0; i < N; i++) {
		fore(x, e[i])er[x].pb(i);
	}

	for (int i = 0; i < N; i++)state[i] = 0;

	//終了時間の降順でdfsをしていく
	vector<pair<int, int>>finli;
	for (int i = 0; i < N; i++) {
		finli.pb({ fin[i],i });
	}
	sort(all(finli));
	reverse(all(finli));
	for (int i = 0; i < N; i++) {
		int v = finli[i].second;
		if (state[v] == 0) {
			dfs2(v, num);
			num++;
		}
	}
}

void add_edges(int x, int y,int sz) {
	e[(x+sz)%(2*sz)].pb(y%(2*sz));
	e[(y+sz)%(2*sz)].pb(x%(2*sz));
}


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

	int N, D;
	cin >> N >> D;
	vector<int>zahyou;
	vector<pair<int,int>>li;
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		li.pb({ x,y });
		zahyou.pb(x);
		zahyou.pb(y);
	}
	sort(all(zahyou));
	zahyou.erase(unique(all(zahyou)), zahyou.end());

	int sz = zahyou.size();

	for (int i = 0; i < N; i++) {
		int x = li[i].first;
		int y = li[i].second;
		li[i].first = lower_bound(all(zahyou), x) - zahyou.begin();
		li[i].second = lower_bound(all(zahyou), y) - zahyou.begin();
	}

	for (int i = 0; i < N; i++) {
		int xidx = li[i].first;
		int yidx = li[i].second;
		add_edges(xidx,yidx,sz);
		add_edges(xidx+sz,yidx+sz,sz);
	}


	for (int i = 0; i < sz; i++) {
		for (int j = i + 1; j < sz; j++) {
			if (zahyou[j] - zahyou[i] >= D)continue;
			add_edges(i+sz,j+sz,sz);
		}
	}

	scc(2*sz);

	//check
	for (int i = 0; i < sz; i++) {
		if (cmp[i] == cmp[i + sz]) {
			puts("No");
			return 0;
		}
	}


	puts("Yes");
	for (int i = 0; i < N; i++) {
		int xidx = li[i].first;
		int yidx = li[i].second;
		if (cmp[xidx + sz] < cmp[xidx])puts(zahyou[xidx]);
		else puts(zahyou[yidx]);
	}



	return 0;
}