A körzeti informatikaversenyen \(N\) versenyző vesz részt neveik sorban \(1, 2, \ldots, N\). Az összes tanuló egyetlen nagy teremben versenyez, amelyben \(N\) számítógép található. Ezek neve is sorban \(1, 2, \ldots, N\). Kezdetben az \(1\) nevű versenyző az \(1\) nevű számítógép mellett ül, \(2\) nevű versenyző az \(2\) nevű számítógép mellett ül stb., és az \(N\) nevű versenyző az \(N\) nevű számítógép mellett ül.

A tanulók meglehetősen készületlenek, és érzékenyek is, ezért folyamatosan panaszkodnak a számítógépek állapotára, a talajvízre meg a huzatra, és kérik, hogy helyezzék át őket egy másik számítógéphez. A verseny folyamán pontosan \(M\) helycsere történt sorban egymás után. Az \(i\)-edik helycsere folyamán (\(1 \leq i \leq M\)) pontosan két tanuló cserél helyet: a versenyző, aki az \(A_i\) számítógép mellett ült, most a \(B_i\) mellé ül, aki pedig a \(B_i\) gépen dolgozott, átül az \(A_i\) számítógéphez. Az is megtörténhet, hogy egy versenyző többször helyet cserél, sőt többször odaül ugyanahhoz a számítógéphez.

A szervező, Programozó Pero nyilvántartást vezet a versenyzők helycseréiről, és minden helycsere után, ha legalább egy versenyző sorszáma \(K\) értéknél nagyobb mértékben különbözik a számítógép sorszámánál, ahol dolgozik, Pero összeráncolja homlokát, mert gyanús neki, miért távolodott el ennyire a versenyző kezdeti számítógépétől. Feladatotok az, hogy minden helycsere után eldöntsétek, Pero összeráncolta -e homlokát.

Bemenet

A szabványos bemenet első sorában az \(N\), \(M\) és \(K\) nemnegatív egész számok állnak, sorban ezek a versenyzők számát, a helycserék számát, és Pero gyanakvási paraméterét jelentik. A következő \(M\) sor mindegyikében két egymástól különböző természetes szám: \(A_i\) és \(B_i\) áll. Ezek a számítógépek sorszámai, amelyeknél dolgozó versenyzők egymással helyet cserélnek.

Kimenet

Kiíratni \(M\) számot, mindegyiket új sorba, mégpedig úgy, hogy az \(i\)-edik szám \(1\) ha az \(i\)-edik helycsere után Pero összeráncolta homlokát, \(0\) , ha nem ráncolta össze.

1. példa

Bemenet

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

Kimenet

0
1
1
0
1

2. példa

Bemenet

10 2 0
1 10
1 10

Kimenet

1
0

A példa magyarázata

Az első példa esetében \(N = 8\), \(M = 5\), \(K= 3\). A tanulók elhelyezkedése a számítógépeken kezdetben 1 2 3 4 5 6 7 8 egy-egy helycsere után pedig

• 1 2 3 6 5 4 7 8 (az elhelyezkedés jó, mert \(|1-1|<K, |2-2| < K, \ldots, |4 - 6| < K\) stb.)

• 1 8 3 6 5 4 7 2 (az elhelyezkedés gyanús, mert a \(8\) jelzésű tanuló a \(2\) gépnél ül, és\(|8 - 2| > K\))

• 1 5 3 6 8 4 7 2 (az elhelyezkedés gyanús, mert a \(2\) jelzésű tanuló a \(8\) gépnél ül, és \(|2 - 8| > K\))

• 1 5 3 6 2 4 7 8 (az elhelyezkedés jó)

• 5 1 3 6 2 4 7 8 (az elhelyezkedés gyanús, mert az \(5\) jelzésű tanuló az \(1\) gépnél ül, és \(|5 - 1| > K\))

Korlátozások

• \(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\) és \(A_i \neq B_i\)

A tesztpéldák 5 független csoportba oszthatók:

• Tesztpéldák, melyek \(20\) pontot érnek: \(N,M \leq 10^3\).
• Tesztpéldák, melyek \(20\) pontot érnek: \(M\leq 10^4\).
• Tesztpéldák, melyek \(20\) pontot érnek: \(K = N - 3\).
• Tesztpéldák, melyek \(20\) pontot érnek: \(K = 0\).
• Tesztpéldák, melyek \(20\) pontot érnek: nincs külön korlátozás.