Метки результатов забега по дереву

После школьной спартакиады была подготовлена модель, которая по времени финиша присваивает результату забега текстовую метку. Например, метками могут быть medal, finish или withdrawn.

Модель уже построена и задана в виде дерева решений. Внутренняя вершина содержит порог времени, а лист содержит готовую метку. Для каждого значения из блока ЗАПРОС требуется определить метку, выданную деревом.

В вершине SPLIT t L R для известного времени финиша x переход выполняется по точному правилу: если x <= t, следующей вершиной становится L, иначе следующей вершиной становится R. Если время обозначено как NA, оно считается пропуском и переход всегда выполняется в правую вершину R. При равенстве времени финиша и порога выбирается левая вершина.

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

Формат ввода

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

Следующие n строк содержат описания вершин. Каждая вершина имеет один из двух видов:

• id LEAF label — лист с номером id и меткой label;
• id SPLIT t left right — внутренняя вершина с номером id, порогом t, номером левой вершины left и номером правой вершины right.

В конце входа записаны q строк блока ЗАПРОС. В каждой строке находится целое время финиша в секундах либо строка NA.

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

Требуется вывести q строк. В строке с номером i должна находиться метка, предсказанная деревом для запроса с номером i.

Ограничения

1 <= n <= 2000.

1 <= q <= 2000.

Номера вершин — целые числа от 1 до n, номер корня равен 1.

Число вершин в корректном полном дереве нечётно.

Для каждой вершины SPLIT: 0 <= t <= 100000, 1 <= left, right <= n, left != right.

Время финиша в запросе является целым числом от 0 до 200000 либо строкой NA.

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