Aamurusko kirjoittaa listaan sanoja yksi kerrallaan. Hän ei halua kirjoittaa samaa sanaa kahdesti. Voisitko auttaa Aamuruskoa huomaamaan, jos sama sana on jo kirjoitettu aiemmin?

Syöte

Ensimmäisellä rivillä on kokonaisluku n: sanojen määrä.

Seuraa n riviä, joista jokaisella on yksi sana. Jokainen sana koostuu merkeistä a–z.

Tuloste

Tulosta jokaiselle sanalle omalle rivilleen joko 10-4, jos sana ei ole vielä listassa, tai QAQ, jos se on esiintynyt aiemmin.

Esimerkki

Syöte:

4
pallo
hattu
pallo
ovi

Tuloste:

10-4
10-4
QAQ
10-4

Rajat

• 1 \le n \le 10^5
• sanojen yhteispituus on enintään 10^6