Problem 2931: yatti

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ă $26$ insule pe care se poate muta, notate cu cele $26$ litere mari ale alfabetului latin (A, B, C, ..., X, Y, Z).

Yatii are $N$ prieteni, fiecare locuiește pe una din cele $26$ de insule. El știe că al $i$ -lea prieten, locuiește pe insula $a_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ă $N$ , șirul $a_1, a_2, \dots, a_N$ . De asemenea, Yatti îți pune $Q$ interogări de forma: Îți dau $l$ și $r$ , dacă aș avea doar prietenii care locuiesc pe pozițiile $a_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 $N$ . Pe a doua linie se află șirul $a_1, a_2, \dots, a_N$ . Pe a treia linie se află numărul $Q$ și pe următoarele $Q$ linii se află câte o pereche $l, r$ separată printr-un spațiu.

Date de ieșire

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

Restricții și precizări

$2 \leq N, Q \leq 100 \ 000$
$a_i \in \{$ A $,$ B $,$ C $, \dots,$ X $,$ Y $,$ Z $\}$ pentru fiecare $i$ de la $1$ la $N$

#	Punctaj	Restricții
1	20	$Q = 1$ , $l = 1$ , $r = N$
2	20	$N, Q \leq 1 \ 000$
3	30	$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 $A$ . Observăm că literele A și G apar ambele de $3$ ori. Cum A este înaintea lui G în ordinea alfabetică, Yatti s-ar muta pe insula A.

La a patra interogare, considerăm valorile $a_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 $3$ prieteni. Așadar, el preferă să se mute pe insula G.

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

Exemplul 2