На Марсе есть небольшое королевство. В королевстве есть несколько городов, некоторые из которых являются областными центрами. Также у королевстве имеется столица, которая может как быть областным центром, так и не быть. Между городами построены дороги с односторонним движением, некоторые из которых красные, а остальные - синие, при этом из каждого города выходит не более одной дороги каждого цвета. Согласно традиции, каждый год король отправляется в поездку из столицы по некоторому маршруту. Этот маршрут всегда состоит из \textbf{L} дорог и должен заканчиваться в одном из областных центров. В историко-эстетических целях последовательность цветов посещенных дорог записывается в летописи. При этом красный обозначается символом '\textbf{0}', а синий - символом '\textbf{1}'. Таким образом получается последовательность из \textbf{L} двоичных цифр. Юный марсианин Васйа изучает историю и ему в руки попались некоторые части летописи, соответствующие времени правления короля Ареса. Васйа обнаружил, что король обязан был выполнять следующие требования: каждый год необходимо выбирать такой маршрут, чтобы его запись была больше, чам в прошлом году, если её прочесть как двоичное число (лидирующие нули считаются допустимыми). В первый год своего правления король имел право выбирать любой маршрут по желанию. Соответственно, если король не сможет найти очередной маршрут, то он должен закончить своё правление. Также проанализировав указы короля, Васйа понял, что Арес был довольно сообразительным и всегда выбирал маршруты так, чтобы править как можно дольше. Однако из-за того, что у Васйы неполная летопись, некоторые вещи остались ему непонятны. Например: - По какому маршруту двигался король в \textbf{K}-й год своего правления (годы правления нумеруются начиная с 1)? - В какой год своего правления Арес двигался по маршруту, записанному строкой \textbf{S}? - Какой маршрут он выбрал следующим после маршрута, записанного строкой \textbf{S}? - Какой маршрут был перед маршрутом, записанным строкой \textbf{S}? Так как Васйа не столь сообразителен, как Арес, он попросил Вас ответить на свои вопросы. Напишите программу, которая могла бы отвечать на такие вопросы. : \textbf{Входные данные} Первая строка входного файла содержит пять целых чисел: \textbf{N}, \textbf{M}, \textbf{F}, \textbf{L}, \textbf{Q} - количество городов, дорого, областных центров; длина маршрута короля и количество вопросов у Васйы (\textbf{1} <= \textbf{N} <= \textbf{50}, \textbf{1} <= \textbf{M} <= \textbf{100S}, \textbf{1} <= \textbf{F} <= \textbf{N}, \textbf{1} <= \textbf{L} <= \textbf{60}, \textbf{1} <= \textbf{Q} <= \textbf{10 000}). Города пронумерованы целыми числами от \textbf{1} до \textbf{N}. Столицей королевства является город с номером \textbf{1}. В следующих \textbf{M} строках дано описание системы дорог - по три целых числа в каждой строке: \textbf{A_i}, \textbf{B_i} и \textbf{C_i}, означающие, что \textbf{i}-тая дорога ведет из города \textbf{A_i} в город \textbf{B_i} и имеет цвет \textbf{C_i} ('\textbf{0}', если дорога красная и '\textbf{1}', если синяя). Следующая строка содержит \textbf{F} различных целых чисел - номера городов, являющихся областными центрами. В каждой из следующих \textbf{Q} строк содержится по одному вопросу в следующем формате: - \textbf{?} \textbf{K} - по какому маршруту двигался король в \textbf{K}-й год своего правления (\textbf{1} <= \textbf{K} <= \textbf{5*10^18})? - \textbf{!} \textbf{S} - в какой год своего правления он двигался по маршруту, записанному строкой \textbf{S}? - \textbf{>} \textbf{S} - какой маршрут Арес выбрал следующим после маршрута, записанного строкой \textbf{S}? - \textbf{<} \textbf{S} - какой маршрут был перед маршрутом, записанным строкой \textbf{S}? \textbf{Формат выходных данных} Выходной файл должен содержать \textbf{T} строк - по одной строке на каждый вопрос. Для вопросов вида \textbf{!} \textbf{S} требуется вывести целое число в десятичной системе счисления. Для остальных типов вопросов нужно вывести строку из \textbf{L} символов '\textbf{0}' и '\textbf{1}' - запись соответствующего маршрута.