学步园

Problem Description

Nobody knows, but N frogs live in Chef's garden.
Now they are siting on the X-axis and want to speak to each other. One frog can send a message to another one if the distance between them is less or equal to K.
Chef knows all P pairs of frogs, which want to send messages. Help him to define can they or not!
Note : More than 1 frog can be on the same point on the X-axis.

Input

The first line contains three integers N, K and P.
The second line contains N space-separated integers A1, A2, ..., AN denoting the x-coordinates of frogs".
Each of the next P lines contains two integers A and B denoting the numbers of frogs according to the input.

Output

For each pair print "Yes" without a brackets if frogs can speak and "No" if they cannot.

Constraints

1 ≤ N, P ≤ 10^5
0 ≤ Ai, K ≤ 10^9
1 ≤ A, B ≤ N

Example

Input:

5 3 3
0 3 8 5 12
1 2
1 3
2 5

Output:

Yes
Yes
No

Explanation

For pair (1, 2) frog 1 can directly speak to the frog 2 as the distance between them is 3 - 0 = 3 <= K .

For pair (1, 3) frog 1 can send a message to frog 2, frog 2 can send it to frog 4 and it can send it to frog 3.
For pair (2, 5) frogs can't send a message under current constraints.

题解

并查集。考虑将点排序，再根据k将点划分入各个集合中。注意：因为已排序过，所以j不需要从i+1开始循环（详见程序中connect函数）。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,k,p,fa[100002];
struct flog{int w,num;} b[100002];
bool kp(const flog &i,const flog &j) {return i.w<j.w;}
void init()
{
	scanf("%d%d%d",&n,&k,&p);
	int i;
	for(i=1;i<=n;i++)
	   {scanf("%d",&b[i].w);
	    b[i].num=i; fa[i]=i;
	   }
	sort(b+1,b+n+1,kp);
}
int find(int x)
{
	if(fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}
void connect()
{
	int i,j=1,r1,r2;
	for(i=1;i<=n;i++)
	   {r1=find(b[i].num);
	    for(;j<=n;j++)
	       {if(j<=i) continue;
			if(b[j].w>b[i].w+k) break;
		    else
		       {r2=find(b[j].num); fa[r2]=r1;}
		   }
	   }
}
void work()
{
	int i,x,y,r1,r2;
	for(i=1;i<=p;i++)
	   {scanf("%d%d",&x,&y);
	    r1=find(x); r2=find(y);
	    if(r1==r2) printf("Yes\n");
	    else printf("No\n");
	   }
}
int main()
{
	init(); connect(); work();
	return 0;
}