Метки профилей теплицы

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

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

Для каждого датчика требуется определить ближайший профиль. Если у датчика известны температура t и влажность h, а у профиля значения T и H, вычисляется квадрат расстояния

D = сумма (x - c)^2 по всем известным у датчика величинам.

То есть при известных обоих значениях D = (t - T)^2 + (h - H)^2; при отсутствии температуры учитывается только (h - H)^2, а при отсутствии влажности — только (t - T)^2. Профиль с наименьшим D становится меткой датчика. Если минимальное расстояние одинаково для нескольких профилей, выбирается профиль с лексикографически меньшим кодом.

Формат ввода

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

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

profile_code T H

Затем идут n строк таблицы показаний датчиков. В каждой строке записаны через пробел код датчика, температура и влажность:

sensor_code t h

Вместо t или h может стоять строка NA.

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

Выведите n строк в порядке показаний датчиков. В каждой строке выведите код датчика, пробел и код выбранного профиля.

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

Ограничения

• 1 <= n <= 2000;
• 1 <= k <= 30;
• температура профиля и датчика, если она известна: целое число от -500 до 800;
• влажность профиля и датчика, если она известна: целое число от 0 до 1000;
• код профиля и код датчика состоят из латинских заглавных букв и цифр, имеют длину от 1 до 8;
• все коды профилей различны, все коды датчиков различны;
• в строке показаний датчика хотя бы одно из значений температуры и влажности не равно NA;
• у профилей пропусков нет.