Метки событий парковки по дереву

На парковке торгового центра для каждого въезда и выезда определяется служебная метка. Готовое решающее дерево хранится в первой таблице, а события парковки — во второй.

У каждого внутреннего узла дерева указан признак, порог и идентификаторы левого и правого потомков. Признаки обозначаются буквами H, F, D: час события, число свободных мест и направление соответственно. Значение направления 0 означает выезд, 1 — въезд.

Для события начинают в узле с идентификатором 1. В узле с признаком P и порогом t берут значение x этого признака. Если значение известно и x <= t, переходят к левому потомку, иначе — к правому. Если значение признака равно NA, также переходят к правому потомку. Процесс повторяется до листа, а ответом является метка этого листа.

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

Формат ввода

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

Следующие k строк содержат таблицу дерева в формате: node_id feature threshold left_id right_id label

Если строка описывает внутренний узел, feature равно H, F или D, threshold — целое число, left_id и right_id — идентификаторы потомков, а label равно -.

Если строка описывает лист, feature равно X, threshold, left_id и right_id равны 0, а label содержит метку листа.

Следующие n строк содержат таблицу событий в формате: event_id direction hour free_spaces

Поля hour и free_spaces могут быть целыми числами или строкой NA.

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

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

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

Ограничения

1 <= k <= 2000, 1 <= n <= 2000.

1 <= node_id, left_id, right_id <= 2000 для внутренних узлов.

1 <= event_id <= 10^9.

direction равно 0 или 1.

Если значение hour не равно NA, то 0 <= hour <= 23.

Если значение free_spaces не равно NA, то 0 <= free_spaces <= 10000.

Для внутреннего узла с признаком H порог находится от 0 до 23, с признаком F — от 0 до 10000, с признаком D — равен 0 или 1.

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