Na okružnom takmičenju iz informatike učestvuje ~N~ takmičara. Njihova imena su ~1, 2, \ldots, N~. Svi takmičari rade u velikoj prostoriji u kojoj se nalazi ~N~ računara u nizu. Imena računara su ~1, 2, \ldots, N~. Na početku, takmičar ~1~ sedi za računarom ~1~, takmičar ~2~ za računarom ~2~, itd., takmičar ~N~ za računarom ~N~.

Kako su takmičari generalno nepripremljeni i fragilni, oni se stalno žale na računare, podzemne vode i promaju i traže da se premeste za neki drugi računar. Preciznije, tokom takmičenja se desilo tačno ~M~ premeštanja, redom. U ~i~-tom premeštanju (~1 \leq i \leq M~) tačno dva takmičara menjaju mesta: takmičar koji je u tom trenutku radio na računaru ~A_i~ sada prelazi na računar ~B_i~ a takmičar koji je u tom trenutku radio na računaru ~B_i~ prelazi na računar ~A_i~. Moguće je da se tokom takmičenja neki takmičar premesti više puta (možda i nekoliko puta na isti računar).

Organizator Programer Pera vodi evidenciju o premeštanju takmičara i svaki put kada postoji bar jedan takmičar čiji se redni broj razlikuje za više od ~K~ od rednog broja računara za kojim taj takmičar trenutno radi, Pera se namršti jer se takmičar baš udaljio od svog početnog računara, što je sumnjivo! Vaš zadatak je da nakon svakog premeštanja odredite da li se Pera namrštio.

Opis ulaza

U prvom redu standardnog ulaza nalaze se nenegativni celi brojevi ~N~, ~M~ i ~K~, redom, koji predstavljaju broj takmičara, broj premeštanja i Perin parametar za sumnju. U narednih ~M~ redova nalaze se po dva različita prirodna broja ~A_i~ i ~B_i~: redni brojevi računara sa kojih se takmičari međusobno premeštaju.

Opis izlaza

Ispisati ~M~ brojeva, svaki u posebnom redu, gde je ~i~-ti broj ~1~ ukoliko se nakon ~i~-tog premeštanja Pera namrštio a ~0~ ukoliko nije.

Primer 1

Ulaz

8 5 3
4 6
8 2
2 5
5 8
1 2

Izlaz

0
1
1
0
1

Primer 2

Ulaz

10 2 0
1 10
1 10

Izlaz

1
0

Objašnjenje primera

Za prvi primer je ~N = 8~, ~M = 5~, ~K= 3~. Raspored učenika po računarima je na početku 1 2 3 4 5 6 7 8 a nakon svakog premeštanja je

• 1 2 3 6 5 4 7 8 (raspored je dobar jer ~|1-1|<K, |2-2| < K, \ldots, |4 - 6| < K~ itd.)
• 1 8 3 6 5 4 7 2 (raspored je sumnjiv jer npr. učenik ~8~ sedi za računarom ~2~ a ~|8 - 2| > K~)
• 1 5 3 6 8 4 7 2 (raspored je sumnjiv jer učenik ~2~ sedi za računarom ~8~ a ~|2 - 8| > K~)
• 1 5 3 6 2 4 7 8 (raspored je dobar)
• 5 1 3 6 2 4 7 8 (raspored je sumnjiv jer učenik ~5~ sedi za računarom ~1~ a ~|5 - 1| > K~)

Ograničenja

• ~2 \leq N,M \leq 3 \cdot 10^5~
• ~0 \leq K \leq 3 \cdot 10^5~
• ~1 \leq A_i, B_i \leq N~ i ~A_i \neq B_i~

Test primeri su podeljeni u 5 disjunktnih grupa:

• U test primerima vrednim ~20~ poena važi ~N,M \leq 10^3~.
• U test primerima vrednim ~20~ poena važi ~M\leq 10^4~.
• U test primerima vrednim ~20~ poena važi ~K = N - 3~.
• U test primerima vrednim ~20~ poena važi ~K = 0~.
• U test primerima vrednim ~20~ poena nema dodatnih ograničenja.