Задача: Эвакуация при пожаре

План эвакуации из здания нарисован в виде плоскости 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-го кабинета.
 

Примеры

Ваш ответ: