Darkwing Duck
Gizli ördək, haqların çempionu, Kölgələrdən çıxır, Darkwing gecəyə sahibdir. Haradasa bir cani plan qurur, amma onun vaxtı bitdi.
Duman buludu və o görünür, sürpriz ustası. O kölgəli maskanın arxasındakı ağıllı kimdir? Heç kim dəqiq bilmir, amma pis adamların bəxti gətirmir.
Çünki Darkwing Duck gəlir!
Və Darkwing Duck sənin köməyinə ehtiyac duyur, dostum. Bəzən pis adamların pis işlərini gördüyü yerdə duman buludundan dəqiq çıxmaq çox çətindir. Təsəvvür et ki, Megavolt şərq tərəfə hücum etməyi planlaşdırır və Mr Banana Brain mütləq qərbdə görünəcək. Bildiyimiz yeganə şey odur ki, canilər həmişə maksimum zərər verməyi planlaşdırır və biz onları dayandırmaq üçün nə edəcəyimizə qərar verməliyik. Şəhər şərqdən qərbə doğru bir sıra binalardan ibarətdir. Darkwing Duck bilir ki, pis adamlar l-ci binadan r-ci binaya qədər olan seqmentdə haradasa görünür, sonra qərbə doğru hərəkət edərək yollarında hər şeyi məhv edir və bu seqmentdə haradasa yoxa çıxırlar. İlk qurban üçün maksimum zərər vermək niyyətində olduqları üçün həmişə ən dəyərli binanı seçirlər, əgər bir neçə seçim varsa, məhv etmək üçün ən dəyərli növbəti binanı seçirlər və s., əgər hələ də bərabərlik varsa, maksimum sayda binanı məhv etməyə çalışırlar. Darkwing Duck-a canilərin hücum yerini dəqiq tapmaqda kömək et.
Giriş verilənləri
Girişin ilk sətrində şəhəri şərqdən qərbə təmsil edən ingilis hərfləri, rəqəmlər və ",", "!", "_", ".", "–" simvollarından ibarət bir sətir var. Sətirin uzunluğu 500000 simvoldan çox deyil. Binanın dəyəri onu təmsil edən simvolun ASCII koduna bərabərdir! İkinci sətirdə N (1 ≤ N ≤ 500000) — sorğuların (canilərin hücumlarının) sayı var. Növbəti N sətirdə 1 ≤ l_i ≤ r_i — canilərin mümkün hücum seqmenti (bu seqmentin tamamilə sətirin içində olduğu təmin edilir). Binalar 1-dən başlayaraq nömrələnir.
Çıxış verilənləri
Hər bir sorğu üçün bir sətirdə bir rəqəm çap etməlisiniz: canilərin hücumunun başlanğıc nöqtəsi. Və güc sizinlə olsun!