Array Rotation and Queries

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 $x$ exists in the sequence, define $\operatorname{idx}(x)$ as the unique position satisfying $A_{\operatorname{idx}(x)}=x$.

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 $-1$, then reverse the order of that interval.

Equivalently, if the interval immediately before the query is

then immediately after the query it becomes

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

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

$T$ case$_1$ case$_2$ $\vdots$ case$_T$

Each case is given in the following format:

$N\ Q$ $x_1\ y_1$ $x_2\ y_2$ $\vdots$ $x_Q\ y_Q$

The $i$-th query is given by two integers $x_i$ and $y_i$. Every query satisfies the guarantees in the statement with respect to the current sequence immediately before that query.

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

• $1\leq T\leq 20$.
• $1\leq N\leq 200\,000$.
• $1\leq Q\leq 5\,000\,000$.
• $-N\leq x_i,y_i\leq N$ ($1\leq i\leq Q$).
• $x_i\neq 0$ and $y_i\neq 0$ ($1\leq i\leq Q$).
• Immediately before the $i$-th query, both $x_i$ and $y_i$ exist in the current sequence and $\operatorname{idx}(x_i)\leq \operatorname{idx}(y_i)$ ($1\leq i\leq Q$).
• The sum of $N$ over all test cases does not exceed $200\,000$.
• The sum of $Q$ over all test cases does not exceed $5\,000\,000$.