Marslı hökmdar#254
Marslı hökmdar
Marsda böyük olmayan bir krallıq var. Bu krallıqda bir neçə şəhər var, bəziləri vilayət mərkəzləridir. Krallıqda həmçinin paytaxt var, hansı ki, vilayət mərkəzi ola bilər və ya olmaya bilər. Şəhərlər tək istiqamətli yollarla birləşdirilib. Yolların bəziləri qırmızı, digərləri isə mavidir. Hər şəhərdən yalnız bir rəngdə bir yol çıxır.
Ənənəyə görə, hər il kral paytaxtdan başlayaraq səfərə çıxır. Səfər yoldan ibarətdir və vilayət mərkəzlərindən birində bitməlidir. Tarixi və estetik məqsədlə, səfərdə gedilən yolların rəng ardıcıllığı salnamədə qeyd olunur. Qırmızı yol '0', mavi yol isə '1' simvolu ilə göstərilir və nəticədə ədəd ikilik rəqəm alınır.
Marslı gənc Vasya tarixi öyrənir. O, kral Aresin dövrünü təsvir edən bəzi salnamə hissələrini tapır. Vasya kralın səfərləri ilə bağlı aşağıdakı tələbləri aşkar edir:
- Hər il kral əvvəlki ildəkindən daha böyük bir ardıcıllığa (yazılışı) malik yeni bir səfər seçməlidir. Ardıcıllıqlar başda sıfırlar olmaqla ikilik ədədlər kimi müqayisə olunur. Birinci il kral istədiyi hər hansı səfəri seçə bilər. - Əgər kral yeni uyğun səfər tapa bilmirsə, hakimiyyəti sona çatır. - Ares hər zaman hakimiyyət müddətini maksimum etmək üçün ən əlverişli səfərləri seçirdi.
Lakin Vasya yalnız salnamənin bəzi hissələrinə malik olduğundan, bəzi məlumatlara aydınlıq gətirə bilmir. Məsələn:
- Kral hakimiyyətinin -ci ilində hansı səfəri edib? (İllər -dən başlayır) - Ares ardıcıllığı ilə səfəri hansı ildə edib? - ardıcıllığından sonra hansı səfəri seçib? - ardıcıllığından əvvəl hansı səfər olub?
Vasya Ares qədər ağıllı olmadığından sizdən bu suallara cavab verməyinizi xahiş edir. Onlara cavab verən proqram yazın.
Birinci sətirdə , , , , ədədləri verilir — şəhərlərin, yolların, vilayət mərkəzlərinin sayı, kralın səfərinin uzunluğu və Vasyanın suallarının sayı (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).
Şəhərlər -dən -ə qədər nömrələnib. Paytaxt nömrəli şəhərdir.
Sonra xətt verilir. Hər biri A_i, B_i, C_i ədədi olmaqla yolun A_i şəhərindən B_i şəhərinə getdiyini və rənginin C_i olduğunu göstərir ('0' - qırmızı, '1' - mavi).
Növbəti xəttdə vilayət mərkəzi olan fərqli şəhərin nömrəsi verilir.
Sonra sətirdə hər biri aşağıdakı formalardan birində olan suallar verilir: - : Kral -cı ildə hansı səfəri edib? (1 \le K \le 5 \times 10^{18}) - : ardıcıllığı ilə səfəri hansı ildə edib? - : ardıcıllığından sonra hansı səfəri seçib? - : ardıcıllığından əvvəl hansı səfər olub?
Səfər uzunluğunda '0' və '1' simvollarından ibarət olur.
Bütün sorğuların doğru və cavabın həmişə mövcud olduğu təmin edilir.
Hər bir sorğu üçün ayrı-ayrı sətirdə:
- tipli suallar üçün bir tam ədəd (il) çıxışa verilir. - Digər suallar üçün isə uzunluğunda ikilik səfər ardıcıllığı yazılır.
Nümunə 1