Марсіанський король#254
Марсіанський король
На Марсі існує невелике королівство з кількома містами, деякі з яких є обласними центрами. Столиця королівства може бути обласним центром, але це не обов'язково. Між містами прокладені односторонні дороги, які бувають червоними або синіми. З кожного міста може виходити не більше однієї дороги кожного кольору.
Щороку король вирушає в подорож зі столиці за певним маршрутом, який завжди складається з доріг і закінчується в одному з обласних центрів. Для історичних цілей послідовність кольорів доріг фіксується в літописі: червоний позначається символом '0', а синій — '1', утворюючи послідовність з двійкових цифр.
Юний марсіанин Вася, вивчаючи історію, знайшов частини літопису з часів правління короля Ареса. Він дізнався, що король мав дотримуватися таких правил:
Щороку обирати маршрут, запис якого більший за попередній, якщо читати його як двійкове число (лідируючі нулі дозволяються).
У перший рік правління король міг обрати будь-який маршрут.
Якщо ж король не міг знайти новий маршрут, він мав завершити своє правління.
Арес завжди обирав маршрути так, щоб правити якомога довше.
Однак через неповну літопис Вася не зрозумів деякі деталі. Наприклад:
Яким маршрутом рухався король у -й рік правління (роки починаються з )?
У який рік свого правління Арес рухався за маршрутом, записаним рядком ?
Який маршрут він обрав після маршруту, записаного рядком ?
Який маршрут був перед маршрутом, записаним рядком ?
Вася звернувся до вас за допомогою, щоб відповісти на ці питання. Напишіть програму, яка зможе дати відповіді.
Перший рядок містить п'ять цілих чисел: , , , , (1 \le N \le 50, 1 \le M \le 100, 1 \le F \le N, 1 \le L \le 60, 1 \le Q \le 10\ 000) — кількість міст, доріг, обласних центрів, довжина маршруту короля і кількість питань від Васі.
Міста пронумеровано від до . Столиця — місто номер .
Наступні рядків описують дороги: у -му рядку три числа A_i, B_i, C_i — з міста A_i в місто B_i проходить дорога кольору C_i ('0' — червона, '1' — синя).
У наступному рядку різних цілих чисел — номери міст, які є обласними центрами.
Далі йде рядків із питаннями у такому форматі:
: яким маршрутом рухався король у -й рік (1 \le K \le 5 \times 10^{18})?
: у який рік був вибраний маршрут ?
: який маршрут було вибрано після маршруту ?
: який маршрут було вибрано до маршруту ?
Маршрут — рядок довжини із символів '0' і '1'.
Гарантується, що всі запити коректні, і відповідь завжди існує.
Для кожного запиту виведіть відповідь в новому рядку:
Для запитів — одне число (рік).
Для інших типів — рядок довжини — запис маршруту.
Приклад 1