Классификация формы шахматиста

После завершения шахматного турнира для каждого участника сохранены две характеристики: набранные очки, умноженные на 10, и число неточностей в партиях. Тренер также указал для каждого участника метку его игровой формы.

Для нового участника известны те же характеристики, но его метка не определена. Требуется определить её методом k ближайших соседей при k = 3.

Для участника i и запроса рассматриваются только характеристики, известные у обоих. Если множество таких характеристик K непусто, расстояние равно квадрату евклидова расстояния: d_i = сумма по j из K величин (x_ij - q_j)^2. Если ни одна характеристика не известна одновременно у участника и у запроса, считается, что d_i = +бесконечность. Выбираются min(3, n) участников с наименьшими расстояниями. При равенстве расстояний раньше выбирается участник, расположенный раньше во входных данных. Меткой запроса становится метка, получившая наибольшее число голосов среди выбранных участников. При равенстве числа голосов выведите лексикографически меньшую метку.

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

Формат ввода

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

В следующих n строках содержатся четыре значения: идентификатор участника, число очков, умноженное на 10, число неточностей и метка игровой формы.

Последняя строка имеет вид QUERY p b, где p — число очков, умноженное на 10, для нового участника, а b — число его неточностей. Вместо p или b может стоять символ -.

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

Выведите одну метку игровой формы для строки запроса.

Ограничения

1 ≤ n ≤ 2000.

Идентификатор участника состоит из строчных и заглавных латинских букв и цифр, его длина от 1 до 20 символов.

Метка состоит из строчных латинских букв, её длина от 1 до 20 символов.

Каждое известное значение очков, умноженных на 10, является целым числом от 0 до 110.

Каждое известное число неточностей является целым числом от 0 до 100.

Вместо каждого числового значения может встречаться символ -. Метка у каждого из n участников всегда задана.