The building evacuation plan is drawn as a
xy plane. The building has
N offices and
M stairs leading to the exit. Coordinates of the
ith cabinet (
\( 1<=i<=N\)) -
\((a_i, b_i)\), and the coordinates of stairs with number
j (
\( 1<=j<=M\ )) -
\((c_j, d_j)\). During a fire alarm, all people in a particular room must evacuate using the nearest stairs. The nearest staircase is determined by the Manhattan distance between two points
\((x_1, y_1)\) and
\(( x_2, y_2)\) by the formula
\(|x_1-x_2| + |y_1-y_2|\). Here
\(|x|\) denotes the absolute value of
x. If there are several nearest stairs for the office, then you need to evacuate using the stairs with the smallest index.
Decide which stairs people in each office should evacuate to.
Input
The first line specifies two integers
N and
M (
\(1<=N,M< ;=50\)). Followed by
N lines, two integers per line - coordinates
\((a_i, b_i)\), then
M lines of two integers numbers in each line -coordinates
\((c_i, d_i)\).
\(-10^8< ;=a_i ,b_i,c_j,d_j<=10^8\).
Imprint
Print
N lines. On the
ith line (
\( 1<=i<=N\)) the index of the stairs used to evacuate from the i-th room must be indicated.
Examples
| # |
Input |
Output |
| 1 |
2 2
20
0 0
-1 0
10 |
2
1 |
| 2 |
3 4
10 10
-10 -10
3 3
1 2
23
3 5
3 5
| 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 |
5
4
3
2
1 |