Nakon što je proveo ceo dan gledajući naučnofantastične filmove, Petar je odlučio da iskoristi ideje i znanje koje je iz njih pokupio i napravi mehaničkog proroka, odnosno mašinu koja odgovara na bilo kakvo da-ne pitanje koje joj se postavi.

Nakon što je napravio proroka, Petar mu je postavio ~N~ pitanja i beležio odgovore koje je dobio. Da ne bi trošio previše papira, svako pitanje je skraćeno obeležio identifikacionim brojem (tako da istim brojevima odgovara isto pitanje -- Petar je neka pitanja postavio više puta). Primetio je da su odgovori koje je dobio kontradiktorni, tj. da je na neka pitanja dobio i odgovor "da" i odgovor "ne".

Petar pretpostavlja da je problem u neispravnoj prostor-vremenskoj ferfucni, zbog koje prorok na svako ~K~-to postavljeno pitanje odgovara suprotno od tačnog odgovora (gde ~2 \leq K \leq N~). Da bi mogao da počne popravke odmah, umesto da čeka da sazna prave odgovore, zamolio vas je da nađete najmanje ~K~ koje odgovara ovoj pretpostavci i dobijenim odgovorima.

Opis ulaza

U prvom redu standardnog ulaza nalazi se jedan prirodan broj ~N~ - broj pitanja koja je Petar postavio. U narednih ~N~ redova nalaze se identifikacioni broj ~i~-tog pitanja ~Q_i~ i odgovor koji je prorok dao ~A_i~. Sve vrednosti ~A_i~ će biti ili "da" ili "ne".

Opis izlaza

U prvom i jedinom redu standardnog izlaza ispisati ~K~ -- najmanju vrednost "perioda" sa kojim je moguće da prorok greši. Ukoliko takvo ~K~ ne postoji, ispisati -1.

Primer 1

Ulaz

5
1 da
2 ne
1 ne
3 da
2 ne

Izlaz

3

Primer 2

Ulaz

3
1 da
1 ne
1 ne

Izlaz

-1

Objašnjenje primera

U prvom primeru, ako su odgovori na pitanja sa identifikacionim brojevima ~1, 2, 3~ redom "da", "ne" i "da", odgovori proroka su konzistentni ako je na treće postavljeno pitanje dao suprotan odgovor (tj. ~K = 3~). Za ~K = 2~ se ne slažu odgovori na prvo i treće pitanje (prorok na njih ne bi odgovorio suprotno), kao ni odgovori na drugo i peto (prorok bi na drugo pitanje odgovorio suprotno a ne peto ne bi).

Ograničenja i podzadaci

• ~1 \leq Q_i \leq 10^9~

Postoje ~3~ podzadataka, u kojima dodatno važi:

• Podzadatak 1 [20 poena]: ~1 \leq N \leq 2000~.
• Podzadatak 2 [35 poena]: ~1 \leq N \leq 100000~, i za sve ~i~ važi ~Q_i \leq 200~.
• Podzadatak 3 [45 poena]: ~1 \leq N \leq 100000~.