#abc057b. [abc057_b]Checkpoints

[abc057_b]Checkpoints

問題文

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

制約

  • 1N,M501≦N,M≦50
  • \-108ai,bi,cj,dj108\-10^8≦a_i,b_i,c_j,d_j≦10^8
  • 入力は全て整数である。

入力

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

NN MM a1a_1 b1b_1 ::
aNa_N bNb_N c1c_1 d1d_1 ::
cMc_M dMd_M

出力

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


入力例 1

2 2
2 0
0 0
-1 0
1 0

出力例 1

2
1

11 番目の学生と各チェックポイント間のマンハッタン距離は以下の通りです。

  • 番号 11 のチェックポイントへのマンハッタン距離は 2(1)+00=3|2-(-1)|+|0-0|=3
  • 番号 22 のチェックポイントへのマンハッタン距離は 21+00=1|2-1|+|0-0|=1

したがって、最も近いチェックポイントの番号は 22 であるため、11 行目には 22 と出力します。

22 番目の学生と各チェックポイント間のマンハッタン距離は以下の通りです。

  • 番号 11 のチェックポイントへのマンハッタン距離は 0(1)+00=1|0-(-1)|+|0-0|=1
  • 番号 22 のチェックポイントへのマンハッタン距離は 01+00=1|0-1|+|0-0|=1

最も近いチェックポイントが複数ある場合は、番号が最も小さいチェックポイントに移動するため、22 行目には 11 と出力します。


入力例 2

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

出力例 2

3
1
2

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


入力例 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