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 <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#define debug(x) cerr << __LINE__ << ' ' << #x << ':' << x << '\n'
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
template<class T> using pque = priority_queue<T, vector<T>, greater<T>>;
constexpr int inf = 1000000010;
constexpr ll INF = 1000000000000000010;
constexpr int mod1e9 = 1000000007;
constexpr int mod998 = 998244353;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
constexpr ll ten(int n) { return n ? 10 * ten(n - 1) : 1; };
int dx[] = { 1,0,-1,0,1,1,-1,-1 }; int dy[] = { 0,1,0,-1,1,-1,1,-1 };
void fail() { cout << "-1\n"; exit(0); } void no() { cout << "No\n"; exit(0); }
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }
template<class T> istream &operator >> (istream &s, vector<T> &v) { for (auto &e : v) s >> e; return s; }
template<class T> ostream &operator << (ostream &s, const vector<T> &v) { for (auto &e : v) s << e << ' '; return s; }

struct fastio {
	fastio() {
		cin.tie(0); cout.tie(0);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(20);
		cerr << fixed << setprecision(20);
	}
}fastio_;

class SCC {
	vector<vector<int>> graph;
	vector<vector<int>> revgraph;
	vector<int> vs;
	vector<bool> used;
public:
	vector<int> cmp;
	SCC(int n) {
		graph = revgraph = vector<vector<int>>(n, vector<int>());
		vs = cmp = vector<int>(n);
		used = vector<bool>(n);
	}
	void add_edge(int from, int to) {
		graph[from].push_back(to);
		revgraph[to].push_back(from);
	}
	void add_edge(int from, int a, int b, int s) {
		a += s; b += s;
		while (a < b) {
			if (a & 1) add_edge(from, s + (a++));
			if (b & 1) add_edge(from, s + (--b));
			a >>= 1; b >>= 1;
		}
	}
	void dfs(int v) {
		used[v] = true;
		for (int i : graph[v]) {
			if (!used[i]) dfs(i);
		}
		vs.push_back(v);

	}
	void rdfs(int v, int k) {
		used[v] = true;
		cmp[v] = k;
		for (int i : revgraph[v]) {
			if (!used[i]) rdfs(i, k);
		}
	}
	int solve() {
		int n = graph.size();
		for (int i = 0; i < n; i++) used[i] = false;
		vs.clear();
		for (int v = 0; v < n; v++) {
			if (!used[v]) dfs(v);
		}
		for (int i = 0; i < n; i++) used[i] = false;
		int k = 0;
		for (int i = n - 1; i >= 0; i--) {
			if (!used[vs[i]]) rdfs(vs[i], k++);
		}
		return k;
	}
};

int main() {
	int n, d;
	cin >> n >> d;
	SCC scc(4 * n);
	vector<int> x(2 * n);
	rep(i, 2 * n) cin >> x[i];
	rep(i, 2 * n) {
		rep(j, 2 * n) {
			if (i == j) continue;
			if (j - i == 1 && i % 2 == 0) {
				scc.add_edge(i * 2 + 1, j * 2);
				scc.add_edge(j * 2 + 1, i * 2);
			}
			else if (abs(x[i] - x[j]) < d) {
				scc.add_edge(i * 2, j * 2 + 1);
			}
		}
	}
	scc.solve();
	vector<int> ans(2 * n);
	rep(i, 2 * n) {
		if (scc.cmp[2 * i] == scc.cmp[2 * i + 1]) no();
		else if (scc.cmp[2 * i] > scc.cmp[2 * i + 1] && (i % 2 == 0 || !ans[i - 1])) ans[i] = 1;
	}
	cout << "Yes\n";
	rep(i, 2 * n) if (ans[i]) cout << x[i] << '\n';
}