题目描述

$xy$ 平面があり、その上に $N$ 人の学生がいて、$M$ 個のチェックポイントがあります。
$i$ 番目の学生がいる座標は $(a_i,b_i)\ (1≦i≦N)$ であり、番号 $j$ のチェックポイントの座標は $(c_j,d_j)\ (1≦j≦M)$ です。
これから合図があり、各学生はマンハッタン距離で一番近いチェックポイントに集合しなければなりません。
2つの地点 $(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\ (1\ ≦i≦N)$ 番目の行には、$i$ 番目の学生が訪れるチェックポイントの番号を出力せよ。

题目大意

有N个学生和M个检查站。

第i个学生的坐标i为ai，bi，编号为j的检查点的坐标为cj,dj。

每个学生都必须去曼哈顿距离最近的检查站。 两点( x1，y1 )和( x2，y2 )之间的曼哈顿距离为| x1 - x2 | + | y1 - y2 |。

如果学生有多个最近的检查点，他/她将选择索引最小的检查点。

每个学生要去哪个检查站？

输入

n,m

接下来n行 ai,bi

接下来m行 cj,dj

输出共n行，每行是检查站的编号

感谢@chengni 提供的翻译

2 2
2 0
0 0
-1 0
1 0

2
1

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

3
1
2

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

5
4
3
2
1

提示

制約

• $1≦N,M≦50$
• $-10^8≦a_i,b_i,c_j,d_j≦10^8$
• 入力は全て整数である。

Sample Explanation 1

$1$ 番目の学生と各チェックポイント間のマンハッタン距離は以下の通りです。 - 番号 $1$ のチェックポイントへのマンハッタン距離は $|2-(-1)|+|0-0|=3$ - 番号 $2$ のチェックポイントへのマンハッタン距離は $|2-1|+|0-0|=1$ したがって、最も近いチェックポイントの番号は $2$ であるため、$1$ 行目には $2$ と出力します。 $2$ 番目の学生と各チェックポイント間のマンハッタン距離は以下の通りです。 - 番号 $1$ のチェックポイントへのマンハッタン距離は $|0-(-1)|+|0-0|=1$ - 番号 $2$ のチェックポイントへのマンハッタン距離は $|0-1|+|0-0|=1$ 最も近いチェックポイントが複数ある場合は、番号が最も小さいチェックポイントに移動するため、$2$ 行目には $1$ と出力します。

Sample Explanation 2

同じ座標に複数のチェックポイントが存在する場合もあります。