Ближайшие визиты парковки до и после стандартизации

Архив парковки состоит из завершённых визитов. Для каждого визита известны идентификатор, минута въезда и длительность стоянки в минутах. Часть старых записей могла быть неполной: значение NA означает, что соответствующий признак неизвестен.

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

В расчётах участвуют только полные архивные записи, то есть записи, у которых не указано NA ни в одном из двух признаков. Для полного архивного визита с признаками (e, d) и нового визита (E, D) расстояние до стандартизации равно евклидову расстоянию sqrt((e-E)^2 + (d-D)^2). После стандартизации каждый признак заменяется формулой z=(x-μ)/σ, где μ — среднее значение этого признака по всем полным архивным записям, а σ=sqrt((1/k) * Σ(x_i-μ)^2) — генеральное стандартное отклонение, k — число полных архивных записей. Затем снова используется евклидово расстояние между двумя парами z-оценок.

При равенстве расстояний выбирается архивный идентификатор, лексикографически меньший в порядке ASCII.

Формат ввода

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

Следующие n строк содержат архивную таблицу в формате id entry_min stay_min:

• id — идентификатор архивного визита;
• entry_min — минута въезда или NA;
• stay_min — длительность стоянки в минутах или NA.

Следующие m строк содержат таблицу новых визитов в том же формате id entry_min stay_min. В строках новых визитов значения entry_min и stay_min всегда являются целыми числами.

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

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

Округление не применяется: выводятся только идентификаторы в точности в исходном виде.

Ограничения

1 ≤ n ≤ 4000, 1 ≤ m ≤ 4000.

Длина каждого идентификатора составляет от 1 до 20 символов. Идентификаторы состоят из латинских букв, цифр, символов _ и -; внутри каждой таблицы они не повторяются.

Если значение не равно NA, то 0 ≤ entry_min ≤ 1439 и 1 ≤ stay_min ≤ 10080.

Полных архивных записей не менее двух. Генеральное стандартное отклонение минут въезда по полным архивным записям строго положительно. Генеральное стандартное отклонение длительностей стоянки по полным архивным записям строго положительно. Поэтому деления на ноль не возникает.