Ближайшая точка выработки солнечных панелей

На солнечной электростанции хранятся наблюдения за условиями работы панелей. Для каждого наблюдения известны освещённость в Вт/м² и температура панели в градусах Цельсия. Некоторые датчики освещённости или температуры могли не передать значение, тогда в таблице записано NA.

Требуется для каждого запроса найти номер наиболее похожего наблюдения из таблицы. Номера наблюдений равны их порядковым номерам во входе, начиная с 1. Перед сравнением оба признака нормируются отдельно методом min-max.

Для каждого признака минимум min и максимум max находятся только по известным значениям этого признака в таблице наблюдений. Известное значение x заменяется на (x - min) / (max - min). Если max = min, нормированное значение признака считается равным 0 для всех точек и запросов. Пропуск NA в наблюдении также заменяется нормированным значением 0. В запросах пропусков нет.

Расстояние между запросом с нормированными признаками (a, b) и наблюдением с нормированными признаками (c, d) равно квадрату евклидова расстояния: (a - c)^2 + (b - d)^2. Выводится номер наблюдения с наименьшим расстоянием. При равенстве наименьших расстояний выбирается наблюдение с меньшим номером. Округление не применяется, так как ответом является целое число.

Формат ввода

В первой строке даны два целых числа n и q — число наблюдений и число запросов.

В следующих n строках даны два значения: освещённость и температура панели для очередного наблюдения. Каждое значение является целым числом или строкой NA.

В следующих q строках даны два целых числа: освещённость и температура панели в запросе.

Формат вывода

Выведите q строк. В строке с номером i выведите номер наблюдения, ближайшего к запросу с номером i.

Ограничения

1 ≤ n ≤ 4000.

1 ≤ q ≤ 20.

Освещённость в наблюдении, если она известна, является целым числом от 0 до 1400.

Температура в наблюдении, если она известна, является целым числом от -40 до 90.

Освещённость в каждом запросе является целым числом от 0 до 1400.

Температура в каждом запросе является целым числом от -40 до 90.

В каждой из двух колонок наблюдений есть хотя бы одно известное значение. Строка наблюдения может содержать один или два пропуска NA.