#456 Array Rotation and Queries

Statement

Statement language

Dadas wrote code that processes the following query in $O(1)$ time. Your task is to do the same.

Let the current sequence be $A=[A_1,A_2,\cdots,A_N]$ . If a value exists in the sequence, define as the unique position satisfying .

A query gives two integers $x$ and $y$ and is processed as follows.

Both $x$ and $y$ exist in the current sequence, and $\operatorname{idx}(x)\leq \operatorname{idx}(y)$ is guaranteed.
Multiply every element in the interval $[\operatorname{idx}(x),\operatorname{idx}(y)]$ by , then reverse the order of that interval.

Equivalently, if the interval immediately before the query is

[x,\ A_{\operatorname{idx}(x)+1},\ \cdots,\ A_{\operatorname{idx}(y)-1},\ y],

then immediately after the query it becomes

[-y,\ -A_{\operatorname{idx}(y)-1},\ \cdots,\ -A_{\operatorname{idx}(x)+1},\ -x].

The initial sequence is $[1,2,\cdots,N]$ . Find the sequence after processing all $Q$ queries.

Input

The input is given from Standard Input in the following format:

$T$ case $_1$ case $_2$

Output

For each test case, print the sequence after processing all queries on one line. Separate consecutive elements with spaces.

Constraints

$1\leq T\leq 20$ .
$1\leq N\leq 200\,000$ .
$1\leq Q\leq 5\,000\,000$ .

Subtasks

#	Score	Constraints
1	9	$N=1$ .
2	18	The sum of $N$ over all test cases does not exceed $2\,000$ . The sum of $Q$ over all test cases does not exceed .

Samples

Input

Output

1 2 -3 4 5
-4 1 2 3

In the first test case, the sequence becomes $[1,-4,-3,-2,5]$ after the first query. It returns to $[1,2,3,4,5]$ after the second query, and becomes after the last query.