Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

На окружном такмичењу из информатике учествује \(N\) такмичара. Њихова имена су \(1, 2, \ldots, N\). Сви такмичари раде у великој просторији у којој се налази \(N\) рачунара у низу. Имена рачунара су \(1, 2, \ldots, N\). Na почетку, такмичар \(1\) седи за рачунаром \(1\), такмичар \(2\) за рачунаром \(2\), итд., такмичар \(N\) за рачунаром \(N\).

Како су такмичари генерално неприпремљени и фрагилни, они се стално жале на рачунаре, подземне воде и промају и траже да се преместе за неки други рачунар. Прецизније, током такмичења се десило тачно \(M\) премештања, редом. У \(i\)-том премештању (\(1 \leq i \leq M\)) тачно два такмичара мењају места: такмичар који је у том тренутку радио на рачунару \(A_i\) сада прелази на рачунар \(B_i\) а такмичар који је у том тренутку радио на рачунару \(B_i\) прелази на рачунар \(A_i\). Могуће је да се током такмичења неки такмичар премести више пута (можда и неколико пута на исти рачунар).

Организатор Програмер Пера води евиденцију о премештању такмичара и сваки пут када постоји бар један такмичар чији се редни број разликује за више од \(K\) од редног броја рачунара за којим тај такмичар тренутно ради, Пера се намршти јер се такмичар баш удаљио од свог почетног рачунара, што је сумњиво! Ваш задатак је да након сваког премештања одредите да ли се Пера намрштио.

Опис улаза

У првом реду стандардног улаза налазе се ненегативни цели бројеви \(N\), \(M\) и \(K\), редом, који представљају број такмичара, број премештања и Перин параметар за сумњу. У наредних \(M\) редова налазе се по два различита природна броја \(A_i\) и \(B_i\): редни бројеви рачунара са којих се такмичари међусобно премештају.

Опис излаза

Исписати \(M\) бројева, сваки у посебном реду, где је \(i\)-ти број \(1\) уколико се након \(i\)-тог премештања Пера намрштио а \(0\) уколико није.

Пример 1

Улаз

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

Излаз

0
1
1
0
1

Пример 2

Улаз

10 2 0
1 10
1 10

Излаз

1
0

Објашњење примера

За први пример је \(N = 8\), \(M = 5\), \(K= 3\). Распоред ученика по рачунарима је на почетку 1 2 3 4 5 6 7 8 а након сваког премештања је - 1 2 3 6 5 4 7 8 (распоред је добар јер \(|1-1|<K, |2-2| < K, \ldots, |4 - 6| < K\) itd.) - 1 8 3 6 5 4 7 2 (распоред је сумњив јер нпр. ученик \(8\) седи за рачунаром \(2\) а \(|8 - 2| > K\)) - 1 5 3 6 8 4 7 2 (распоред је сумњив јер ученик \(2\) седи за рачунаром \(8\) а \(|2 - 8| > K\)) - 1 5 3 6 2 4 7 8 (распоред је добар) - 5 1 3 6 2 4 7 8 (распоред је сумњив јер ученик \(5\) седи за рачунаром \(1\) а \(|5 - 1| > K\))

Ограничења

Тест примери су подељени у 5 дисјунктних група: