Ближайшие записи парковки по двум метрикам

У торгового центра сохраняются записи о посещениях парковки. Для каждой записи известны номер талона, минута въезда и минута выезда в пределах суток.

Иногда один из датчиков не срабатывает. В такой записи соответствующее время равно -1, и такая запись не может участвовать в поиске ближайшей.

Для каждого запроса известны минута въезда и минута выезда нового автомобиля. Нужно определить номера двух талонов: ближайшего по манхэттенскому расстоянию и ближайшего по евклидову расстоянию.

Для записи с координатами (a, b) и запроса (x, y) манхэттенское расстояние равно |a - x| + |b - y|. Евклидово расстояние равно sqrt((a - x)^2 + (b - y)^2).

Если минимальное расстояние достигается у нескольких записей, выбирается запись с меньшим номером талона. Гарантируется, что для каждого запроса существует хотя бы одна запись с известными временем въезда и выезда.

Формат ввода

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

В следующих n строках даны три целых числа id, entry, exit — номер талона, минута въезда и минута выезда. Значение -1 означает, что соответствующее время неизвестно.

В следующих q строках даны два целых числа entry_query и exit_query — минута въезда и минута выезда в запросе.

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

Для каждого запроса выведите в отдельной строке два целых числа: номер талона, ближайшего по манхэттенскому расстоянию, и номер талона, ближайшего по евклидову расстоянию.

Округление не применяется, так как выводятся номера талонов.

Ограничения

1 <= n <= 2000.

1 <= q <= 2000.

Номера талонов id различны и лежат в диапазоне от 1 до 10^9.

Для каждой сохранённой записи entry и exit равны -1 либо являются целыми числами от 0 до 1439.

Для каждого запроса entry_query и exit_query являются целыми числами от 0 до 1439.

В каждой строке нет строковых полей, все значения являются целыми числами.