Смена кластера посещения сайта

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

Посещения уже были отнесены к одному из двух кластеров. Отдельная таблица содержит профили кластеров: координаты их центров по тем же двум показателям. Одна итерация состоит в одновременном пересчёте меток всех посещений по неизменным профилям кластеров.

Для посещения с известным множеством показателей \(K\) расстояние до профиля кластера \(c\) равно квадрату евклидова расстояния только по известным показателям: \[ d^2=\sum_{j\in K}(x_j-c_j)^2. \] Если показатель посещения равен -, он не входит в сумму. В каждой строке посещения известен хотя бы один показатель.

Гарантируется, что после итерации метка изменится ровно у одного посещения. Требуется вывести его идентификатор. При равенстве расстояний до двух кластеров выбирается кластер с номером 1. Выведите целое число, без дробной части.

Формат ввода

В первой строке дано целое число n — количество строк в таблице посещений.

В следующих n строках находятся четыре значения: visit_id, duration, pages, old_cluster — идентификатор посещения, длительность сессии, число просмотренных страниц и прежняя метка кластера. Значения duration и pages имеют вид целого числа или символа -.

В следующих двух строках находится таблица профилей кластеров. Каждая строка содержит три целых числа cluster_id, center_duration, center_pages — номер кластера и две координаты его профиля. Строки профилей могут идти в любом порядке. В таблице присутствуют ровно профили кластеров 1 и 2.

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

Выведите visit_id единственного посещения, которое после пересчёта получит метку, отличающуюся от old_cluster.

Ограничения

1 ≤ n ≤ 2000.

1 ≤ visit_id ≤ 10^9, все идентификаторы посещений различны.

0 ≤ duration ≤ 10000, если вместо него не записан символ -.

0 ≤ pages ≤ 10000, если вместо него не записан символ -.

old_cluster и cluster_id равны 1 или 2.

0 ≤ center_duration, center_pages ≤ 10000.

В каждой строке посещения хотя бы одно из полей duration, pages не равно -. Длина каждого числового поля не превышает 10 символов, символ пропуска имеет длину 1.