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