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>
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
 
template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 1e9+7;
constexpr long long inf = 3e18;

struct SCC{
	vector<vector<int>>G,rG;
	vector<bool>used;
	vector<int>vs;
	void addEdge(int x,int y){
		G[x].push_back(y);
		rG[y].push_back(x);
	}
	void dfs(int x){
		used[x]=true;
		for(int i:G[x])if(!used[i])dfs(i);
		vs.push_back(x);
	}
	vector<int>cmp;
	void rdfs(int v,int k){
		used[v]=true;
		cmp[v]=k;
		for(int i:rG[v])if(!used[i])rdfs(i,k);
	}
	void scc(){
		fill(all(used),false);
		rep(i,len(G))if(!used[i])dfs(i);
		fill(all(used),false);
		int k=0;
		rev(i,len(vs))if(!used[vs[i]])rdfs(vs[i],k++);
	}
	SCC(int N):G(N),rG(N),used(N),cmp(N){}
};

int N,D;
int X[1005][2];
bool ng[1005][2];
signed main(){
	cin.tie(0);ios::sync_with_stdio(false);
	cin>>N>>D;
	rep(i,N)cin>>X[i][0]>>X[i][1];
	SCC scc(2*N);
	rep(i,N)for(int j=i+1;j<N;j++)rep(k,2)rep(l,2){
		if(abs(X[i][k]-X[j][l])<D){
			scc.addEdge((1-k)*N+i,l*N+j);
			scc.addEdge((1-l)*N+j,k*N+i);
		}
	}
	scc.scc();
	rep(i,N){
		if(scc.cmp[i]==scc.cmp[i+N]){
			cout<<"No\n";return 0;
		}
	}
	cout<<"Yes\n";
	rep(i,N){
		cout<<X[i][scc.cmp[i]>scc.cmp[i+N]]<<"\n";
	}
}