You are given an unweighted, undirected graph $$$G$$$ with $$$n$$$ nodes and $$$m$$$ edges. The graph $$$G$$$ contains no self-loops or multiple edges.

We denote the node set of $$$G$$$ as $$$V$$$. For any node subset $$$V' \subseteq V$$$, the corresponding induced subgraph, denoted by $$$G[V']$$$, is defined as follows:

$$$G[V']$$$ is the graph whose node set is $$$V'$$$, and whose edge set consists of all edges in $$$G$$$ with both endpoints in $$$V'$$$.

Your task is to answer $$$q$$$ queries. Each query provides three integers $$$l$$$, $$$r$$$, and $$$k$$$. Denoting $$$V'=\{l,l+1,\ldots,r\}$$$, you need to find the $$$k$$$-th smallest value among $$$f(l,G[V'])$$$, $$$f(l+1,G[V'])$$$, $$$\ldots$$$ , $$$f(r,G[V'])$$$ (i.e., the $$$k$$$-th value in increasing order; repeated values are counted multiple times).

Here, $$$f(u,G[V'])=\bigoplus_{(u,v)\in G[V']}v$$$. In other words, it is the bitwise XOR value of the labels of all adjacent nodes of node $$$u$$$ in graph $$$G[V']$$$.

You might want to read the notes for a better understanding.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1.5 \cdot 10^4$$$). The description of the test cases follows.

Each test case begins with two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 1.5 \cdot 10^5$$$, $$$1 \leq m \leq 1.5 \cdot 10^5$$$) — the number of nodes and edges, respectively.

The next $$$m$$$ lines each contain two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$), representing an undirected edge between nodes $$$u_i$$$ and $$$v_i$$$.

The next line contains a single integer $$$q$$$ ($$$1 \leq q \leq 1.5 \cdot 10^5$$$) — the number of queries.

Each of the next $$$q$$$ lines contains three integers $$$l$$$, $$$r$$$, and $$$k$$$ ($$$1 \leq l \leq r \leq n$$$, $$$1 \le k \le r-l+1$$$), defining a query about the induced subgraph $$$G[\{l,\ldots,r\}]$$$.

It is guaranteed that the graph contains no self-loops or multiple edges.

It is guaranteed that the sum of $$$n$$$,$$$m$$$, and $$$q$$$ over all test cases does not exceed $$$1.5 \cdot 10^5$$$, respectively.

Output

For each test case, output $$$q$$$ integers, representing the answer for each query.

Note

In the first test case, the input graph $$$G$$$ is the one in the following picture.

$\text{[math]}$ The given graph $$$G$$$.

In the first query, the induced subgraph $$$G[\{1,2\}]$$$ is the one in the following picture. We can see that nodes $$$1$$$ and $$$2$$$ have no adjacent nodes. Thus, $$$f(1,G[\{1,2\}])=f(2,G[\{1,2\}])=0$$$. The $$$2$$$-nd smallest value is $$$0$$$.

$\text{[math]}$ $$$G[\{1,2\}]$$$.

In the second query, the induced subgraph $$$G[\{1,2,3\}]$$$ is the one in the following picture. We can see that $$$f(1,G[\{1,2,3\}])=3$$$, $$$f(2,G[\{1,2,3\}])=3$$$, and $$$f(3,G[\{1,2,3\}])=1 \oplus 2=3$$$. The $$$1$$$-st smallest value is $$$3$$$.

$\text{[math]}$ $$$G[\{1,2,3\}]$$$.

In the third query, the induced subgraph $$$G[\{2,3,4\}]$$$ is the one in the following picture. We can see that $$$f(2,G[\{2,3,4\}])=3 \oplus 4=7$$$, $$$f(3,G[\{2,3,4\}])=2 \oplus 4=6$$$, and $$$f(4,G[\{2,3,4\}])=2 \oplus 3=1$$$. The $$$3$$$-rd smallest value is $$$7$$$.

$\text{[math]}$ $$$G[\{2,3,4\}]$$$.

Induced Subgraph Queries

Examples