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 "bits/stdc++.h"

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <unordered_map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<complex>
#include<assert.h>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, double> pid;
typedef pair<double, int> pdi;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;

const double EPS = 1e-9;

struct SCC {
	int V;
	vector<vector<int>> SC;		//強連結成分リスト(トポロジカルソート)
	vector<int> SCID;			//各頂点が属する連結成分ID

	vector<vector<int>> G, RG;
	vector<int> NUM;
	vector<bool> used;

	SCC(int V) :V(V)
	{
		SC.resize(V);
		SCID = vector<int>(V, -1);
		G = vector<vector<int>>(V);
		RG = vector<vector<int>>(V);
		used = vector<bool>(V, false);
	}

	void add_edge(int x, int y)
	{
		G[x].push_back(y);
		RG[y].push_back(x);
	}

	void dfs(int v)
	{
		used[v] = true;
		for (auto e : G[v])
		{
			if (!used[e])dfs(e);
		}
		NUM.push_back(v);
	}

	void revdfs(int v, int idx)
	{
		int i; 
		used[v] = true;
		SCID[v] = idx;
		SC[idx].push_back(v); 
		for (auto e : RG[v])
		{
			if (!used[e])revdfs(e, idx);
		}
	}

	void scc()
	{
		int c = 0; 
		fill(all(used), false);
		for (int i = 0; i < V; i++)
		{
			if (!used[i]) dfs(i);
		}
		fill(all(used), false);
		for (int i = NUM.size() - 1; i >= 0; i--)
		{
			if (!used[NUM[i]]) 
			{
				revdfs(NUM[i], c); 
				sort(all(SC[c]));
				c++;
			}
		}
		SC.resize(c);
	}
};

signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N, D;
	cin >> N >> D;
	SCC scc(2 * N);

	vector<pii> P(N);
	rep(i, 0, N)cin >> P[i].first >> P[i].second;

	rep(i, 0, N)
	{
		rep(j, 0, N)
		{
			if (i == j)continue;

			if (abs(P[i].first - P[j].first) < D)
			{
				scc.add_edge(2 * i, 2 * j + 1);
				scc.add_edge(2 * j, 2 * i + 1);
			}
			if (abs(P[i].first - P[j].second) < D)
			{
				scc.add_edge(2 * i, 2 * j);
				scc.add_edge(2 * j + 1, 2 * i + 1);
			}
			if (abs(P[i].second - P[j].first) < D)
			{
				scc.add_edge(2 * i + 1, 2 * j + 1);
				scc.add_edge(2 * j, 2 * i);
			}
			if (abs(P[i].second - P[j].second) < D)
			{
				scc.add_edge(2 * i + 1, 2 * j);
				scc.add_edge(2 * j + 1, 2 * i);
			}
		}
	}

	scc.scc();

	bool ok = true;
	rep(i, 0, N)
	{
		if (scc.SCID[2 * i] == scc.SCID[2 * i + 1])
		{
			ok = false;
		}
	}

	if (!ok)
	{
		cout << "No" << endl;
	}
	else
	{
		cout << "Yes" << endl;
		rep(i, 0, N)
		{
			if (scc.SCID[2 * i] < scc.SCID[2 * i + 1])
			{
				cout << P[i].second << endl;
			}
			else
			{
				cout << P[i].first << endl;
			}
		}
	}

	return 0;
}