题目描述

There are $N$ students and $M$ checkpoints on the $xy$-plane.
The coordinates of the $i$-th student $(1 \leq i \leq N)$ is $(a_i,b_i)$, and the coordinates of the checkpoint numbered $j$ $(1 \leq j \leq M)$ is $(c_j,d_j)$.
When the teacher gives a signal, each student has to go to the nearest checkpoint measured in Manhattan distance.
The Manhattan distance between two points $(x_1,y_1)$ and $(x_2,y_2)$ is $|x_1-x_2|+|y_1-y_2|$.
Here, $|x|$ denotes the absolute value of $x$.
If there are multiple nearest checkpoints for a student, he/she will select the checkpoint with the smallest index.
Which checkpoint will each student go to?

在 $xy$ 这个平面上有 $N$ 个学生和 $M$ 个检查点。
编号为 $i$ -th 的学生 $(1 \leq i \leq N)$ 的坐标是 $(a_i,b_i)$ ，编号为 $j$ $(1 \leq j \leq M)$ 的检查点的坐标是 $(c_j,d_j)$ 。
当教师发出信号时，每个学生都必须前往以_曼哈顿距离_为单位的最近检查点。
两点 $(x_1,y_1)$ 和 $(x_2,y_2)$ 之间的曼哈顿距离为 $|x_1-x_2|+|y_1-y_2|$ 。
这里， $|x|$ 表示 $x$ 的绝对值。
如果一个学生有多个最近的检查点，他会选择指数最小的检查点。
每个学生会去哪个检查点？

输入格式

输入内容按以下格式标准输入：

$N$ $M$
$a_1$ $b_1$
$:$
$a_N$ $b_N$
$c_1$ $d_1$
$:$
$c_M$ $d_M$

输出格式

打印 $N$ 行。
第 $i$ -th 行 $(1 \leq i \leq N)$ 应该包含第 $i$ -th 个学生要去的检查点的索引。

样例 #1

样例输入 #1

2 2
2 0
0 0
-1 0
1 0

样例输出 #1

2
1

样例 #2

样例输入 #2

3 4
10 10
-10 -10
3 3
1 2
2 3
3 5
3 5

样例输出 #2

3
1
2

样例 #3

样例输入 #3

5 5
-100000000 -100000000
-100000000 100000000
100000000 -100000000
100000000 100000000
0 0
0 0
100000000 100000000
100000000 -100000000
-100000000 100000000
-100000000 -100000000

样例输出 #3

5
4
3
2
1

说明

数据规模与约定

• $1 \leq N,M \leq 50$
• $-10^8 \leq a_i,b_i,c_j,d_j \leq 10^8$
• 所有输入值均为整数。

样例 $1$ 解释

第一个学生与每个检查点之间的曼哈顿距离为

• 对于检查点 $1$ ： $|2-(-1)|+|0-0|=3$
• 对于检查点 $2$ ： $|2-1|+|0-0|=1$

最近的检查点是检查点 $2$ 。因此，输出的第一行应包含 $2$ 。

第二名学生与每个检查点之间的曼哈顿距离为

• 对于检查点 $1$ ： $|0-(-1)|+|0-0|=1$
• 对于检查点 $2$ ： $|0-1|+|0-0|=1$

当有多个最近检查点时，学生将前往索引最小的检查点。因此，输出结果的第二行应包含 $1$ 。

样例 $2$ 解释

同一坐标上可能有多个检查点。