Marsda böyük olmayan krallıq var. Bu krallıqda bəziləri vilayət mərkəzləri olan bir neçə şəhər var. Həmçinin krallıqda paytaxt şəhəri var ki, o, həm vilayət mərkəzi ola bilər, həm də olmaya bilər. Şəhərlər arasında birtərəfli hərəkət zolağı olan yollar çəkilmişdir ki, onların bəziləri qırmızı, qalanları isə mavi rənglidir. Eyni zamanda hər şəhərdən hər rəngli birdən artıq olmayan sayda yol çıxır. Ənənəyə görə, hər il kral paytaxtdan başlayaraq müəyyən bir marşrutla səyahətə çıxır. Bu marşrut həmişə \textbf{L} yoldan ibarət olur və vilayət mərkəzlərindən birində qurtarmalıdır. Tarixi-estetik məqsədlə gedilən yolların rəngləri ardıcıllığı salnamələrə yazılır. Bu zaman qırmızı rəngli yollar \textbf{“0”} simvolu, mavi yollar isə \textbf{“1”} simvolu ilə işarə olunur. Beləliklə, \textbf{L} sayda ikili rəqəmlər ardıcıllığı alınır. Marslı gənc Vasya tarixi öyrənir və onun əlinə əlyazmanın kral Apesin hökmdarlığı dövrünə aid olan bəzi hissələri düşür. Vasya müəyyənləşdirir ki, kral aşağıdakı tələbləri yerinə yetirməyə borclu imiş: hər il elə marşrut seçilməlidir ki, onu ikilik ədəd kimi oxuduqda (əvvəldə gələn sıfırlara icazə verilir ) yazılışı əvvəlki ildəkindən böyük olsun. Öz hakimiyyətinin birinci ilində kral arzusuna uyğun olaraq istənilən marşrutu seçə bilər. Əgər kral uyğun növbəti marşrutu seçə bilmirsə, onda o, hakimiyyətdən getməlidir. Həmçinin kralın fərmanlarını təhlil edən Vasya anladı ki, Ares kifayət qədər zəkalıdır və həmişə marşrutu elə seçir ki, mümkün qədər çox hökmranlıq etsin. Lakin Vasyada əlyazma tam olmadığından bəzi şeylər onun üçün qaranlıq qalırdı. Məsələn: - Öz hakimiyyətinin \textbf{K-}cı ilində kral hansı marşrutla hərəkət edib(hakimiyyət illəri 1-dən başlayaraq nömrələnir)? - Öz hakimiyyətinin hansı ilində Ares \textbf{S}-si sətirdə yazılmış marşrutla hərəkət edib? \textbf{- S}-si sətirdə yazılmış marşrutdan sonra o, hansı marşrutu seçib? - \textbf{S}-si sətirdə yazılmış marşrutdan əvvəl hansı marşrut olub? Vasya Ares qədər zəkalı olmadığından öz suallarına cavab verməyi sizdən xahiş edir. Bu suallara cavab verə bilən proqramı yazın. \InputFile Giriş faylının birinci sətrində şəhərlərin, yolların, vilayət mərkəzlərinin miqdarı, kralın marşrutunun uzunluğu və Vasyanın suallarının sayı olan beş tam\textbf{ N}, \textbf{M}, \textbf{F}, \textbf{L}, \textbf{Q} ədədləri yerləşir. (\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}). Şəhərlər \textbf{1-}dən\textbf{ N-}dək tam ədədlərlə nömrələnir. Krallığın paytaxt şəhəri \textbf{1} nömrəlidir. Sonrakı \textbf{M} sətrin hər birində üç tam \textbf{A_i}, \textbf{B_\{i \}}və \textbf{C_i} ədədləri olmaqla yollar sistemi təsvir edilir: \textbf{i-}ci yol \textbf{A_i} şəhərindən \textbf{B_\{i \}}şəhərinə aparır və\textbf{ C_i} rənglidir(əgər yol qırmızı rənglidirsə, '\textbf{0}', əgər mavi rənglidirsə, onda '\textbf{1}'). Sonrakı sətirdə \textbf{F} müxtəlif tam ədəd - vilayət mərkəzləri olan şəhərlərin nömrələri yerləşir. Sonrakı \textbf{Q} sayda sətrin hər birində aşağıdakı formatda suallar yerləşir: - \textbf{?} \textbf{K} - Öz hakimiyyətinin \textbf{K-}cı ilində kral hansı marşrutla hərəkət edib (\textbf{1} <= \textbf{K} <= \textbf{5*10^18})? - \textbf{!} \textbf{S} - Öz hakimiyyətinin hansı ilində o, \textbf{S}-si sətirdə yazılmış marşrutla hərəkət edib? - \textbf{>} \textbf{S} -\textbf{ S}-si sətirdə yazılmış marşrutdan sonra Ares hansı marşrutu seçib? - \textbf{<} \textbf{S} - \textbf{S}-si sətirdə yazılmış marşrutdan əvvəl hansı marşrut olub? \OutputFile Çıxış faylında hər bir suala bir sətir\textbf{ }olmaqla\textbf{ T }sayda sətir yerləşməlidir. \textbf{!} \textbf{S} şəklində olan suallar üçün çıxışa onluq say sistemində olan tam ədədin verilməsi tələb olunur. Digər şəkillərdə olan suallar üçün çıxışa uyğun marşrutun yazılışı olan və \textbf{L} sayda '\textbf{0}' və '\textbf{1}' simvoldan ibarətdir sətir vermək lazımdır.