配点 : $200$ 点

問題文

$xy$ 平面があり、その上に $N$ 人の学生がいて、$M$ 個のチェックポイントがあります。 $i$ 番目の学生がいる座標は $(a_i,b_i) (1 \leq i \leq N)$ であり、番号 $j$ のチェックポイントの座標は $(c_j,d_j) (1 \leq j \leq M)$ です。
これから合図があり、各学生はマンハッタン距離で一番近いチェックポイントに集合しなければなりません。 2つの地点 $(x_1,y_1)$ と $(x_2,y_2)$ 間のマンハッタン距離は $|x_1-x_2|+|y_1-y_2|$ で表されます。 ここで、$|x|$ は $x$ の絶対値を表します。 ただし、一番近いチェックポイントが複数ある場合には、番号が最も小さいチェックポイントに移動することとします。 合図の後に、各学生がどのチェックポイントに移動するかを求めてください。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$a_1$ $b_1$

$:$

$a_N$ $b_N$

$c_1$ $d_1$

$:$

$c_M$ $d_M$

出力

解答を $N$ 行に出力せよ。 $i (1 \leq i \leq N)$ 番目の行には、$i$ 番目の学生が訪れるチェックポイントの番号を出力せよ。

2 2
2 0
0 0
-1 0
1 0

2
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$ と出力します。

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