Description

Steve 正穿梭在两个世界当中，不妨称这两个世界为 A 世界和 B 世界。 A 世界和B 世界各有 n 个传送门，每个传送门有一个坐标 $(x_i,y_i)$。当 Steve 进入某个世界位于$(x_i, y_i)$ 的传送门时，他将被传送到另一个世界中与 $(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 世界的传送门与进入的传送门的距离是多少。

Input Format

从文件 portal.in 中读入数据。

第一行包含两个整数 $n$ 和 $d$，中间用一个空格隔开。

接下来 $n$ 行，每行两个整数 $x, y$，中间用一个空格隔开，表示 A 世界中每个传送门的坐标 $(x, y)$。

接下来 $n$ 行，每行两个整数 $x, y$，中间用一个空格隔开，表示 B 世界中每个传送门的坐标 $(x, y)$。

Output Format

输出到文件 portal.out 中。

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

Sample

样例输入1

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

样例输出1

1
3
2

样例输入2

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

样例输出2

1
3
4

样例3

见选手目录下的 portal/portal3.in 与 portal/portal3.ans。

Hint

对于 $20\%$ 的数据， $1 \le n \le 100$；

对于 $40\%$ 的数据， $1 \le n \le 1000$；

对于另外 $20\%$ 的数据， $0 \le x_i, y_i, d \le 1000$；

对于 $100\%$ 的数据， $1 \le n \le 100000$， $0 \le x_i, y_i, d \le 10^8$。