You are given an undirected graph consisting of $n$ vertices and $m$ edges. The vertices are numbered from zero: $0, 1, \dots, n - 1$. You are required to process $q$ queries. Each query provides a pair $(u, v)$ and asks you to erase the edge $(u, v)$ from the graph. If there is no such edge in the graph (for example, if $u = v$), do nothing. After each query, print whether the graph is connected or not.
Input
The input contains several test cases. The first line contains a single integer $t$ ($1 \le t \le 5 \cdot 10^5$), the number of test cases. The description of the test cases follows.
The first line of each test case contains three integers $n$, $m$, and $q$ ($2 \le n \le 10^6$, $1 \le m, q \le 10^6$): the number of vertices, edges, and queries, respectively.
Each of the next $m$ lines contains two integers $u_i$ and $v_i$ ($0 \le u_i, v_i < n$), representing an edge between $u_i$ and $v_i$. There are no loops and no parallel edges in the graph.
Each of the next $q$ lines describes a query. However, the query parameters $u_j$ and $v_j$ are not provided directly. Instead, the $j$-th of these lines contains two integers $a_j$ and $b_j$ ($0 \le a_j, b_j < n$). Suppose that the answer to the $k$-th query is $c_k = 1$ if the graph is connected or $c_k = 0$ otherwise. Then $u_j$ and $v_j$ are generated according to the formulae:
$$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.$$
The sum of all $n$, the sum of all $m$, and the sum of all $q$ across all test cases do not exceed $10^6$.
Output
For each test case, print $q$ lines with integers $c_1, \dots, c_q$: the answers to the queries.
Example
Sample Input 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
Sample Output 1
0 0 1 1 0 0
Note
In the first test case, the queries ask to delete the edges $(0, 0)$ (it does not exist) and $(0, 1)$.
In the second test case, the queries ask to delete the edges $(0, 1)$, $(2, 0)$ (it does not exist), $(3, 0)$, and $(0, 3)$ (it is already deleted by the previous operation).