14090번 - RAM 다국어

Mirku su hakeri provalili u računalo iskorištavanjem Shellshock propusta te podizanjem voltaže u sustavu uništili gotovo sav RAM osim posljednja 2MB. Mirko u računalu ima točno 26 tvrdih diskova označenih velikim slovima engleske abecede od 'A' do 'Z'. Na sreću, Mirko ima ogroman dnevnik pristupa podacima na tvrdim diskovima koji se sastoji od niza oznaka tvrdih diskova. Analizirao je napad hakera na sljedeći način:

• Dnevnik je podijelio na N manjih datoteka S₁ do S_N, koje može učitati u RAM. Svaka od njih je niz velikih slova engleske abecede.
• Datoteke je učitavo jednu za drugom te je nakon učitane datoteke S_i izračunao približno koliko puta su hakeri pristupili tvrdom disku H_i u posljednjih K_i pristupa u cijelom dnevniku do datoteke S_i, uključivo.

Mirko je ponosan jer je vješto uspio izračunati odgovore na sve upite koji su ga zanimali te razotkrio namjere hakera. Kako vas hakeri ne bi uhvatili nespremne, vaš izazov je napisati program koji će dati približne odgovore na Mirkove upite uz samo 2MB RAM-a. 

U prvom retku nalazi se prirodan broj N (1 ≤ N ≤ 200 000).

Sljedećih 2N redaka podijeljeni su na N grupa od 2 retka:

• U prvome od njih nalazi se niz velikih slova engleske abecede S_i (1 ≤ |S_i| ≤ 4 000)
• U drugome se nalaze znak H_i (veliko slovo engleske abecede), oznaka tvrdog diska te broj pristupa K_i (1 ≤ K_i ≤ Σⁱ_j=1|s_j|)

Napomena: Ukupna količina podataka u ulazu bit će manja od 200MB. 

U N redaka izlaza ispište približne odgovore na N Mirkovih upita. Neka je A_i vaš odgovor, a T_i točan odgovor. Vaš odgovor smatramo približnim ako vrijedi T_i ≤ A_i < 2T_i. Iznimno, ako je točan odgovor T_i jednak nuli, tada i vaš odgovor A_i mora biti jednak nuli.

Napomena: Memorijsko ograničenje za ovaj zadatak je samo 2MB. 

Pojašnjenje: Potpuni dnevnik možemo dobiti spajanjem datoteka:

BAAB|AABB|ZA

Odgovor na 1. upit je broj pristupa tvrdom disku B u označenom podnizu: BAAB|AABB|ZA
Odgovor na 2. upit je broj pristupa tvrdom disku A u označenom podnizu: BAAB|AABB|ZA
Odgovor na 3. upit je broj pristupa tvrdom disku Z u označenom podnizu: BAAB|AABB|ZA