План эвакуации из здания нарисован в виде плоскости
xy. В здании
N кабинетов и
M лестниц, ведущих к выходу. Координаты
i-го кабинета (
\( 1<=i<=N\)) -
\((a_i, b_i)\), а координаты лестниц с номером
j (
\( 1<=j<=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 (
\(1<=N,M<=50\)). Далее идет
N строк по два целых числа в кажой строке - координаты
\((a_i, b_i)\), затем
M строк по два целых числа в кажой строке - координаты
\((c_i, d_i)\).
\(-10^8<=a_i ,b_i,c_j,d_j<=10^8\).
Выходные данные
Выведите
N строк. В
i-й строке (
\( 1<=i<=N\)) должен быть указан индекс лестницы, по которой эвакуируются из i-го кабинета.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 2
2 0
0 0
-1 0
1 0 |
2
1 |
| 2 |
3 4
10 10
-10 -10
3 3
1 2
2 3
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 |