배열 회전과 쿼리

다다스는 다음 쿼리를 한 번당 $O(1)$에 처리하는 코드를 작성했다. 여러분도 해 보자.

현재 수열을 $A=[A_1,A_2,\cdots,A_N]$이라 하자. 수열에 값 $x$가 존재할 때, $A_{\operatorname{idx}(x)}=x$를 만족하는 유일한 위치를 $\operatorname{idx}(x)$라 정의한다.

두 정수 $x,y$가 주어지는 쿼리는 다음과 같이 처리한다.

• 현재 수열에 $x$와 $y$가 모두 존재하며, $\operatorname{idx}(x)\leq \operatorname{idx}(y)$임이 보장된다.
• 구간 $[\operatorname{idx}(x),\operatorname{idx}(y)]$의 원소에 각각 $-1$을 곱한 뒤, 이 구간의 순서를 뒤집는다.

즉, 쿼리 직전의 해당 구간이

였다면, 쿼리 직후에는

가 된다.

초기 수열은 $[1,2,\cdots,N]$이다. $Q$개의 쿼리를 모두 처리한 뒤의 수열을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

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

$i$번 쿼리는 두 정수 $x_i,y_i$로 주어진다. 각 쿼리는 그 직전의 현재 수열에 대해 문제의 보장 조건을 만족한다.

각 테스트 케이스마다, 모든 쿼리를 처리한 뒤의 수열을 한 줄에 출력한다. 수열의 원소는 공백으로 구분한다.

• $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$이고 $y_i\neq 0$이다 ($1\leq i\leq Q$).
• $i$번 쿼리 직전에 현재 수열에 $x_i,y_i$가 모두 존재하며, $\operatorname{idx}(x_i)\leq \operatorname{idx}(y_i)$이다 ($1\leq i\leq Q$).
• 모든 테스트 케이스에 대한 $N$의 합은 $200\,000$ 이하이다.
• 모든 테스트 케이스에 대한 $Q$의 합은 $5\,000\,000$ 이하이다.