yatti

Time limit: 0.3s Memory limit: 128MB Input: yatti.in Output: yatti.out

Cu toții am auzit de Yeti, creatura care trăiește în Munții Himalaya. Totuși, nu mulți știu și de inamicul său, Yatti.

Yatti trăiește în Arhipelagul Maldive, la mare. Acesta a trăit liniștit pentru mii de ani pe o insulă, dar din cauza încălzirii globale și a ridicării nivelului apei din mări și oceane, acesta trebuie să se mute pe altă insulă.

Există 2626 insule pe care se poate muta, notate cu cele 2626 litere mari ale alfabetului latin (A, B, C, ..., X, Y, Z).

Yatii are NN prieteni, fiecare locuiește pe una din cele 2626 de insule. El știe că al ii-lea prieten, locuiește pe insula aia_i. El vrea să se mute pe o insulă pe care trăiesc cât mai mulți din prieteni săi. În caz că există mai multe insule pe care trăiesc la fel de mulți oameni, el se va muta pe cea minimă în ordinea aflabetică.

Cerință

Se dă NN, șirul a1,a2,,aNa_1, a_2, \dots, a_N. De asemenea, Yatti îți pune QQ interogări de forma: Îți dau ll și rr, dacă aș avea doar prietenii care locuiesc pe pozițiile al,al+1,al+2,,ara_l, a_{l+1}, a_{l+2}, \dots, a_r, pe ce insulă m-aș muta? (Citiți explicațiile exemplului pentru clarificare).

Date de intrare

Pe prima linie a fișierului de intrare yatti.in se află numărul NN. Pe a doua linie se află șirul a1,a2,,aNa_1, a_2, \dots, a_N. Pe a treia linie se află numărul QQ și pe următoarele QQ linii se află câte o pereche l,rl, r separată printr-un spațiu.

Date de ieșire

Să se afișeze în fișierul yatti.out QQ linii, pe linia ii fiind răspunsul la a ii-a întrebare.

Restricții și precizări

  • 2N,Q100 0002 \leq N, Q \leq 100 \ 000
  • ai{a_i \in \{A,, B,, C,,, \dots, X,, Y,, Z}\} pentru fiecare ii de la 11 la NN
# Punctaj Restricții
1 20 Q=1Q = 1, l=1l = 1, r=Nr = N
2 20 N,Q1 000N, Q \leq 1 \ 000
3 30 ai{a_i \in \{A,, B}\}
4 30 Fără restricții suplimentare

Exemplul 1

yatti.in

9
ABBAGAGGE
6
1 9
1 4
2 3
5 8
4 7
9 9

yatti.out

A
A
B
G
A
E

Explicații

La prima interogare, trebuie să vedem pe ce insulă s-ar muta Yatti dacă am considera toate valorile din șirul AA. Observăm că literele A și G apar ambele de 33 ori. Cum A este înaintea lui G în ordinea alfabetică, Yatti s-ar muta pe insula A.

La a patra interogare, considerăm valorile a5,a6,a7,a8a_5, a_6, a_7, a_8, adică G, A, G, G dacă s-ar muta pe insula A, ar fi alături de un prieten, d-ar dacă s-ar muta pe insula G, Yatti ar fi alături de 33 prieteni. Așadar, el preferă să se mute pe insula G.

La ultima interogare, considerăm doar valoarea a9=a_9 = E. Așadar, s-ar muta pe insula E.

Exemplul 2

yatti.in

5
ABBAB
3
1 5
2 4
1 4

yatti.out

B
B
A

Log in or sign up to be able to send submissions!