Задача: Эвакуация при пожаре
План эвакуации из здания нарисован в виде плоскости 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 |
Ваш ответ: