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 <vector>
#include <stack>
#include <cstddef>
#include <algorithm>

struct strongly_connected_component {
	using size_type = std::size_t;
private :
	size_type num;
	std::vector<std::vector<size_type>> g, scc;
	std::vector<size_type> low, order, index;
	std::vector<bool> instack;
	std::stack<size_type> sta;

	void chmin (size_type &a, const size_type &b) noexcept {
		if (a > b) a = b;
	}

	void dfs (size_type v) noexcept {
		low[v] = order[v] = ++num;
		sta.push(v); instack[v] = true;
		for (const size_type &u : g[v]) {
			if (order[u] == 0) {
				dfs(u);
				chmin(low[v], low[u]);
			} else if (instack[u]) {
				chmin(low[v], order[u]);
			}
		}
		if (low[v] == order[v]) {
			scc.push_back(std::vector<size_type>());
			while (true) {
				const size_type u = sta.top();
				sta.pop(); instack[u] = false;
				scc.back().push_back(u);
				if (u == v) break;
			}
		}
	}

public :
	explicit strongly_connected_component (size_type n)
	noexcept : num(0), g(n), scc(), low(n, 0), order(n, 0), index(n), instack(n, false), sta() { }

	void add_edge (size_type v, size_type u) noexcept {
		g[v].push_back(u);
	}

	size_type solve () noexcept {
		for (size_type v = 0; v < g.size(); v++) if (not order[v]) dfs(v);
		std::reverse(scc.begin(), scc.end());
		for (size_type i = 0; i < scc.size(); i++) {
			for (const size_type &v : scc[i]) index[v] = i;
		}
		return scc.size();
	}

	const std::vector<std::vector<size_type>> &get_scc () const noexcept {
		return scc;
	}

	size_type size () const noexcept {
		return scc.size();
	}

	const size_type &operator[] (size_type v) const noexcept {
		return index[v];
	}

};


#include <vector>
#include <cstddef>

struct two_sat {
	using size_type = std::size_t;
private :
	strongly_connected_component scc;
	std::vector<bool> answer;

public :
	two_sat (size_type n) noexcept : scc(n << 1), answer(n) { }

	void add_clause (size_type a, bool f, size_type b, bool g) noexcept {
		scc.add_edge(a << 1 | not f, b << 1 | g);
		scc.add_edge(b << 1 | not g, a << 1 | f);
	}

	bool satisfiable () noexcept {
		scc.solve();
		for (size_type i = 0; i < answer.size(); i++) {
			if (scc[i << 1 | 0] == scc[i << 1 | 1]) return false;
			answer[i] = (scc[i << 1 | 0] < scc[i << 1 | 1]);
		}
		return true;
	}

	bool get (const size_type i) const noexcept {
		return answer[i];
	}

};



#include <vector>
#include <cmath>
#include <iostream>

int main() {
	int n, d;
	std::cin >> n >> d;
	std::vector<int> x(n), y(n);
	for (int i = 0; i < n; i++) {
		std::cin >> x[i] >> y[i];
	}
	
	two_sat sat(n);
	
	auto f = [&] (int a, int b) {
		return std::abs(a - b) < d;
	};
	
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (f(x[i], x[j])) sat.add_clause(i, 1, j, 1);
			if (f(x[i], y[j])) sat.add_clause(i, 1, j, 0);
			if (f(y[i], x[j])) sat.add_clause(i, 0, j, 1);
			if (f(y[i], y[j])) sat.add_clause(i, 0, j, 0);
		}
	}
	
	if (sat.satisfiable()) {
		std::cout << "Yes" << '\n';
		for (int i = 0; i < n; i++) {
			std::cout << (sat.get(i) ? y[i] : x[i]) << '\n';
		}
	} else {
		std::cout << "No" << '\n';
	}
	
	return 0;
}