Swapity Swapity Swap

문제

Farmer John's $NN$ cows ($1\le N\le {10}^{5}1\backslash le\; N\backslash le\; 10^5$) are standing in a line. The $ii$th cow from the left has label $ii$ for each $1\le i\le N1\backslash le\; i\backslash le\; N$.

Farmer John has come up with a new morning exercise routine for the cows. He has given the cows $MM$ pairs of integers $(L_1,R_1)\dots (L_M,R_M)(L\_1,R\_1)\; \backslash ldots\; (L\_M,\; R\_M)$, where $1\le M\le 1001\; \backslash leq\; M\; \backslash leq\; 100$. He then tells the cows to repeat the following $MM$-step process exactly $KK$ ($1\le K\le {10}^{9}1\backslash le\; K\backslash le\; 10^9$) times:

• For each $ii$ from $11$ to $MM$:
  • The sequence of cows currently in positions $L_i\dots R_{i}L\_i\; \backslash ldots\; R\_i$ from the left reverse their order.

After the cows have repeated this process exactly $KK$ times, please output the label of the $ii$th cow from the left for each $1\le i\le N1\backslash le\; i\backslash le\; N$.

입력

The first line contains $NN$, $MM$, and $KK$. For each $1\le i\le M1\backslash le\; i\backslash le\; M$, line $i+1i+1$ line contains $L_{i}L\_i$ and $R_{i}R\_i$, both integers in the range $1\dots N1\; \backslash ldots\; N$, where .

출력

On the $ii$th line of output, print the $ii$th element of the array after the instruction string has been executed $KK$ times.

힌트

Initially, the order of the cows is $[1,2,3,4,5,6,7][1,2,3,4,5,6,7]$ from left to right. After the first step of the process, the order is $[1,5,4,3,2,6,7][1,5,4,3,2,6,7]$. After the second step of the process, the order is $[1,5,7,6,2,3,4][1,5,7,6,2,3,4]$. Repeating both steps a second time yields the output of the sample.

7 2 2
2 5
3 7

1
2
4
3
5
7
6