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

В доме сравнивают изменение показаний электросчётчиков за один расчётный период. Для каждого счётчика известны начальные и конечные показания по дневному и ночному тарифам.

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

Для каждого счётчика с номером id определяются два признака: d — расход по дневному тарифу, n — расход по ночному тарифу. Если хотя бы одно из четырёх показаний счётчика равно -1, показание считается пропущенным, а такой счётчик не участвует в поиске ближайших.

Для заданного счётчика t требуется найти среди остальных счётчиков два ближайших: один по манхэттенскому расстоянию, другой по евклидову расстоянию. Для счётчиков с признаками (d1, n1) и (d2, n2) манхэттенское расстояние равно |d1-d2|+|n1-n2|, а евклидово расстояние равно sqrt((d1-d2)^2+(n1-n2)^2).

Если минимальное расстояние достигается у нескольких счётчиков, выбирается счётчик с меньшим номером. Если подходящих счётчиков нет, для соответствующего расстояния выводится -1. Округление не применяется, так как выводятся номера счётчиков.

Формат ввода

В первой строке находятся два целых числа n и t: количество счётчиков и номер заданного счётчика.

Следующие n строк образуют первую таблицу. В каждой строке записаны три целых числа: номер счётчика id, начальное дневное показание day_start, начальное ночное показание night_start.

Следующие n строк образуют вторую таблицу. В каждой строке записаны три целых числа: номер счётчика id, конечное дневное показание day_end, конечное ночное показание night_end.

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

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

Ограничения

1 <= n <= 2000.

1 <= t <= 10^9.

Номера счётчиков — целые числа от 1 до 10^9, все номера в каждой таблице различны.

Обе таблицы содержат один и тот же набор из n номеров, а номер t присутствует в обеих таблицах.

Каждое показание является целым числом от -1 до 10^9.

У заданного счётчика t все четыре показания известны. Для каждого счётчика без пропусков выполняется day_end >= day_start и night_end >= night_start.