Fişierul intrare/ieşire:	abba.in, abba.out	Sursă	Junior Challenge 2019
Autor	Mircea Donciu	Adăugată de	Junior Challenge 2019 •JuniorChallenge2019
Timp execuţie pe test	0.125 sec	Limită de memorie	524288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Abba

X isi petrecea cei 4 ani in Institutia Teoretica de Informatica in asteptarea unei diplome ca ar fi absolvit "liceul".

In timpul sau liber (practic tot timplul sau era liber), a dat de scena urmatoare:

Copiii de la uman se jucau cu niste cuvinte, dar fara sa inteleaga foarte bine despre ce e vorba (daca stiau mai bine poate nu s-ar fi dus la uman).
Fiecare copil spune la randul sau o propozitie (un sir de cuvinte), dupa urmatoarea regula:

1. Primul copil: a___________________________________________________b
2. Al 2-lea copil: a_________________________ab________________________b
3. Al 3-lea copil: a__________aab____________ab___________abb__________b
4. Al 4-lea copil: a___aaab___aab____aabab___ab___ababb___abb___abbb__b

Altfel spus, primul copil spune cuvintele 'a' si 'b', si dupa el fiecare copil repeta ce a zis cel dinaintea lui, adaugand intre fiecare doua cuvinte concatenarea acestora.

X isi pune mai multe intrebari, care pot fi formulate informatic sub forma de mai jos.

Intrebarea este un cuvant, si raspunsul pentru aceasta este al catelea copil spune acel cuvant pentru prima data, si al catelea cuvant este din propozitia lui, respectiv -1 daca acel cuvant nu apare deloc.

Date de intrare

Prima linie contine Q, numarul de cuvinte la care se gandeste X.
Urmatoarele Q linii contin fiecare cate un cuvant.

Date de ieşire

Pentru fiecare din cele Q cuvinte, pe cate o linie, se afiseaza fie x y insemnand ca prima aparitie a cuvantului este la al x-lea copil, si cuvantul este al y-lea din lista copilului x modulo 10⁹ + 7, fie -1 daca nu apare deloc.

Restricţii

• 1 ≤ Q ≤ 10⁴
• Suma lungimilor celor Q cuvinte la care se gandeste X nu depaseste 10⁶.
• Cuvintele la care se gandeste X sunt formate din literele mici ale alfabetului englez.
• Raspunsul trebuie afisat modulo 10⁹ + 7.

Subtaskuri

1. 10 puncte: suma lungimilor este cel mult 1000, se garanteaza ca toate cuvintele apar, si apar pentru prima data in primele 10 propozitii. (testul 1)
2. 20 puncte: toate cuvintele apar, si apar pentru prima data in primele 14 propozitii. (testele 2 şi 3)
3. 10 puncte: toate cuvintele apar, si apar pentru prima data in primele 100 de propozitii, in primele 100 cuvinte ale acelei propozitii si au lungimea cel mult 100. (testul 4)
4. 30 de puncte: cuvintele la care se gandeste X sunt alese pseudo-aleator: oricare doua cuvinte existente de aceasi lungime au aceasi probabilitate sa fie alese, si oricare doua cuvinte neexistente de aceasi lungime au aceasi probabilitate sa fie alese. (testele 5-7)
5. 30 de puncte: se aplică restricţiile iniţiale (testele 8-10)

Exemplu

Explicaţie

• Uitandu-ne pe diagrama de mai sus, observam ca primele aparitii ale cuvintelor 1-4 sunt (1, 1), (1, 2), (3, 2) respectiv (2, 2)
• Se poate demonstra ca nu o sa apara niciodata cuvantul 'ba' nici 'abc', deci raspunsul este -1.

Cum se trimit solutii?