In mod oarecum contraintuitiv pentru o democratie pura cum este Serbanistanul, acest sistem permite unui candidat sa castige presedintia chiar daca acesta a adunat in total mai putine voturi decat adversarul sau. Sarcina voastra in aceasta problema este sa detectati aceasta posibilitate.

Serbanistanul este initial inexistent (dar totusi democratic). In fiecare an dintre urmatorii N componenta sa se schimba cu exact un stat: fie apare un stat nou, fie unul din cele existente se hotaraste sa paraseasca Serbanistanul. Este posibil ca la diferite momente de timp structura Serbanistanului sa cauzeze ambiguitati in procesul alegerilor: este posibil sa existe egalitate de voturi la nivelul unui stat, la nivelul greutatii totale sau la nivelul votului popular total. Din acest motiv ne vom limita la a studia doar situatiile *clare*. Spunem ca Serbanistanul se afla intr-o situatie *clara* doar daca au loc *toate* conditiile urmatoare:

Serbanistanul este initial inexistent (dar totusi democratic). In fiecare an dintre urmatorii $N$ componenta sa se schimba cu exact un stat: fie apare un stat nou, fie unul din cele existente se hotaraste sa paraseasca Serbanistanul. Este posibil ca la diferite momente de timp structura Serbanistanului sa cauzeze ambiguitati in procesul alegerilor: este posibil sa existe egalitate de voturi la nivelul unui stat, la nivelul greutatii totale sau la nivelul votului popular total. Din acest motiv ne vom limita la a studia doar situatiile *clare*. Spunem ca Serbanistanul se afla intr-o situatie *clara* doar daca au loc *toate* conditiile urmatoare:

- Numarul de locuitori al fiecarui stat este impar.
- Numarul total de locuitori ai Serbanistanului este impar

h2. Restricţii
* $1 ≤ N ≤ 200.000$

* $1 ≤ people[i], weight[i] ≤ 10^4^$

* $1 ≤ people[i], weight[i] ≤ 10^9^$
* Teste in valoare de $50%$ din punctaj au $1 ≤ N ≤ 1500$.

h2. Exemplu