Du får en oriktad graf som består av $n$ hörn och $m$ kanter. Hörnen är numrerade från noll: $0, 1, \dots, n - 1$. Du ska behandla $q$ frågor. Varje fråga ger ett par $(u, v)$ och ber dig ta bort kanten $(u, v)$ från grafen. Om det inte finns någon sådan kant i grafen (till exempel om $u = v$), gör ingenting. Efter varje fråga ska du skriva ut huruvida grafen är sammanhängande eller inte.
Indata
Indata innehåller flera testfall. Den första raden innehåller ett enda heltal $t$ ($1 \le t \le 5 \cdot 10^5$), antalet testfall. Beskrivningen av testfallen följer.
Den första raden i varje testfall innehåller tre heltal $n$, $m$ och $q$ ($2 \le n \le 10^6$, $1 \le m, q \le 10^6$): antalet hörn, kanter respektive frågor.
Var och en av de följande $m$ raderna innehåller två heltal $u_i$ och $v_i$ ($0 \le u_i, v_i < n$), som representerar en kant mellan $u_i$ och $v_i$. Det finns inga öglor och inga parallella kanter i grafen.
Var och en av de följande $q$ raderna beskriver en fråga. Frågeparametrarna $u_j$ och $v_j$ ges dock inte direkt. Istället innehåller den $j$-te av dessa rader två heltal $a_j$ och $b_j$ ($0 \le a_j, b_j < n$). Antag att svaret på den $k$-te frågan är $c_k = 1$ om grafen är sammanhängande eller $c_k = 0$ annars. Då genereras $u_j$ och $v_j$ enligt formlerna:
$$u_j = (2^{j-2}c_1 + 2^{j-3}c_2 + \dots + 2^1 c_{j-2} + 2^0 c_{j-1} + a_j) \bmod n,$$
$$v_j = (3^{j-2}c_1 + 3^{j-3}c_2 + \dots + 3^1 c_{j-2} + 3^0 c_{j-1} + b_j) \bmod n.$$
Summan av alla $n$, summan av alla $m$ och summan av alla $q$ över alla testfall överstiger inte $10^6$.
Utdata
För varje testfall, skriv ut $q$ rader med heltalen $c_1, \dots, c_q$: svaren på frågorna.
Exempel
Exempelindata 1
2 3 1 2 0 1 0 0 0 1 4 4 4 0 1 1 2 2 3 0 3 0 1 1 3 0 0 2 3
Exempelutdata 1
0 0 1 1 0 0
Notering
I det första testfallet ber frågorna om att ta bort kanterna $(0, 0)$ (den existerar inte) och $(0, 1)$.
I det andra testfallet ber frågorna om att ta bort kanterna $(0, 1)$, $(2, 0)$ (den existerar inte), $(3, 0)$ och $(0, 3)$ (den har redan tagits bort av föregående operation).