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:

using namespace std;

#define visual

#ifdef visual
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <assert.h>
#include <functional>
#include <math.h>
#include <string>
#include <ctime>
#endif
#ifndef visual
#include <bits/stdc++.h>
#endif

typedef long long ll;


struct twosat {

	vector<bool> vis = {};
	vector<int> cc, L;
	vector<vector<int> > G;
	vector<bool> ans;
	int n, cz;

	void visit(int v) {
		if (vis[v]) return;
		vis[v] = 1;
		for (auto u : G[v])
			visit(u);
		L.push_back(v);
	}

	inline void assign(int v, int r) {
		if (cc[v]) return;
		cc[v] = r;
		for (auto u : G[v ^ 1])
			assign(u ^ 1, r);
		ans[v / 2] = v & 1;
	}

	twosat(int n) { this->n = n, cz = 0, G.resize(2 * n), ans.resize(n), vis.resize(2 * n), cc.resize(2 * n); }

	inline void either(int x1, bool v1, int x2, bool v2) {
		x1 = x1 << 1 | v1, x2 = x2 << 1 | v2;
		G[x1 ^ 1].push_back(x2);
		G[x2 ^ 1].push_back(x1);
	}

	inline void implies(int x1, bool v1, int x2, bool v2) {
		either(x1, false, x2, true);
	}

	vector<bool> solve() {
		int n = G.size() / 2;


		for (int i = 0; i < 2 * n; ++i)
			visit(i);
		vis = vector<bool>(n);
		for (int i = L.size() - 1; i >= 0; --i) {
			if (!cc[L[i]])
				assign(L[i], ++cz);
		}
		for (int i = 0; i < n; ++i)
			if (cc[2 * i] == cc[2 * i + 1])
				return {};
		return ans;
	}

};


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

    int n, d;
	cin >> n >> d;
	twosat t(n);

	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		v.push_back({x, y});
	}
	for (int i = 0; i < n; i++) {
		for (int j = i+1; j < n; j++) {
			
			if (abs(v[i].first - v[j].first) < d) {
				t.either(i, true, j, true);
			}
			if (abs(v[i].second - v[j].first) < d) {
				t.either(i, false, j, true);
			}
			if (abs(v[i].first - v[j].second) < d) {
				t.either(i, true, j, false);
			}
			if (abs(v[i].second - v[j].second) < d) {
				t.either(i, false, j, false);
			}
		}
	}
	auto ans = t.solve();
	if (!ans.size()) {
		cout << "No";
		return 0;
	}
	cout << "Yes" << endl;
	for (int i = 0; i < ans.size(); i++) {
		if(ans[i]) cout << v[i].second << endl;
		if (!ans[i]) cout << v[i].first << endl;
	}


}