Autocomplete

Implementirajte funkcionalnost, ki se bo uporabljala v urejevalniku besedila kot autocomplete funkcija. Podan je slovar besed z njihovo pomembnostjo, ki odraža pogostost uporabe. Napišite program, ki bo prebral slovar in nato učinkovito odgovarjal na poizvedbe o najpomembnejši besedi, ki se začne s podano predpono (upoštevamo tudi besedo, ki se povsem ujema s predpono). Slovar vsebuje same različne besede. Prav tako so pomembnosti besed sama različna cela števila.

Omejitve podatkov:

• $1 \leq N \leq 10^6$ in $1 \leq M \leq 10^6$
• $1 \leq |S_i| \leq 10^5$ in $1 \leq |T_i| \leq 10^5$
• $\sum |S_i| \leq 10^6$ in $\sum |T_j| \leq 10^6$
• $1 \leq P_i \leq 10^9$

Vhodni in izhodni podatki:

Prva vrstica vsebuje število besed $N$ v slovarju, ki so nato podane v naslednjih $N$ vrsticah. V $i$-ti ($i = 1..N$) sledeči vrstici je poleg $i$-te besede $S_i$ še s presledkom ločena pomembnost te besede $P_i$. Besede so poljubni nizi sestavljeni iz malih črk angleške abecede in niso omejene na dejanske angleške ali slovenske besede. Sledi število poizvedb $M$, ki so podane v naslednjih vrsticah z enim nizom $T_j$.

Za vsako poizvedbo izpišite v svoji vrstici zaporedno številko $i$ tiste besede, ki se začne z nizom $T_j$ in ima med vsemi takimi besedami največjo pomembnost. V primerih, ko take besede v slovarju sploh ni, izpišite 0.

Zaradi velike količine vhodnih in izhodnih podatkov predlagamo, da odgovore na vsako poizvedbo shranite v seznam in jih na koncu izpišete vse naenkrat. Izmenjava pisanja in branja namreč povzroči splakovanje izhoda, tako kot uporaba endl.

Primer vhoda:

7
algoritem 20
drevo 1
zaba 3
zebra 10
algebra 4
alge 8
program 5
4
alge
x
a
zeb

Pravilen izhod:

6
0
1
4