Description

Steve正穿梭在两个世界当中，不妨称这两个世界为A世界和B世界。A世界和B世界各有n个传送门，每个传送门有一个坐标（xi,yi）。当Steve进入某个世界位于（xi,yi）的传送门时，他将被传送到另一个世界中与（x,y）的y坐标差不超过d的所有传送门中，距离（x,y）最近的传送门。其中，（x,y）与（x',y'）的y坐标差定义为|y-y'|,(x,y)和(x',y')的距离定义为|x-x'|+|y-y'|。如果距离最近的传送门有多个，则到达任意一个。如果没有满足条件的传送门，则B世界会创建一个位于相同坐标(x,y)的传送门（新建的传送门不影响其他传送门的传送关系）。
Steve想知道从A世界的每一个传送门进入，分别能到达B世界的哪一个传送门，然而由于Steve可能到达多个和他们进入的传送门距离相等的传送门，因此他只希望你告诉他，从A世界的每一个传送门进入，能到达B世界的传送门与进入的传送门的距离是多少。

Format

Input

从文件portal.in中读入数据。
第一行包含两个整数n和d，中间用一个空格隔开。
接下来n行，每行两个整数x，y，中间用一个空格隔开，表示A世界中每个传送门的坐标（x,y）.
接下来n行，每行两个整数x，y，中间用一个空格隔开，表示B世界中每个传送门的坐标（x,y）.

Output

输出到portal.out中。
输出n行，每行一个整数，其中第i个整数表示A世界中第i个传送门（按输入顺序）进入后会被传送到的B世界中的传送门的距离，特别地，如果不存在满足条件的传送门，则B世界会创建一个位于相同坐标(x,y)的传送门，应输出0.

Sample 1

Input

3 4
1 4
3 2
4 2
1 3
1 1
4 4

Output

1
3
2

【样例1解释】

Sample 2

Input

3 1
1 4
3 2
4 2
1 3
1 1
4 4

Output

1
3
4

Limitation

1s, 524288KiB for each test case.
对于20%的数据， 1<=n<=100
对于40%的数据， 1<=n<=1000
对于另外20%的数据，0<=xi,yi,d<=1000
对于100%的数据， 1<=n<=100,000,0<=xi,yi,d<=100,000,000