Repeated Cow Reversal Permutation

Farmer John's $N$ cows (numbered $1$ through $N$ from left to right) are standing in a line. He has devised a new morning exercise routine using $M$ pairs of integers $(L_1,R_1),\ldots,(L_M,R_M)$. In each round, for every $i$ from $1$ to $M$, the cows in positions $L_i$ through $R_i$ (inclusive) have their order reversed. This entire sequence of $M$ reversal steps is repeated $K$ times.

After the $K$ rounds the cows are in a new order. Output the label of the cow in each position from left to right.

Note: If the cows are initially arranged as $[1,2,\dots,N]$, then one complete round of operations produces a permutation $P$ on the positions. The final positions of the cows correspond to applying the permutation $P$ exactly $K$ times. In other words, if a cow originally at position $i$ ends up at position $P^K(i)$, then the cow at position $P^K(i)$ will have label $i+1$. The permutation exponentiation can be computed in $O(N\log K)$ time using the standard binary exponentiation method.

Input Constraints:

• $1\le N\le 10^5$
• $1\le M\le 100$
• $1\le K\le 10^9$

inputFormat

The first line contains three integers $N$, $M$, and $K$. Each of the following $M$ lines contains two integers $L_i$ and $R_i$ describing a reversal operation.

All indices are 1-indexed.

outputFormat

Output $N$ lines, each containing a single integer --- the label of the cow at that position after $K$ rounds of operations.

sample

7 2 1
2 5
3 7

1
5
7
6
2
3
4