P6148 [USACO20FEB] Swapity Swapity Swap S

Farmer John’s $N$ cows ($1\leq N\leq 10^5$) are standing in a line. For each $1\leq i\leq N$, the ID of the $i$-th cow from left to right is $i$. Farmer John has come up with a new morning exercise plan for the cows. He gives the cows $M$ pairs of integers $(L_1,R_1)\ldots (L_M,R_M)$, where $1\leq M\leq 100$. He asks them to repeat the following process, which consists of $M$ steps, a total of $K$ times ($1\leq K\leq 10^9$): For each $i$ from $1$ to $M$: - Reverse the order of the cows currently in positions $L_i\ldots R_i$ from left to right. - After the cows repeat this process $K$ times, output, for each $1\leq i\leq N$, the ID of the $i$-th cow from left to right.

The first line contains $N$, $M$, and $K$. For each $1\leq i\leq M$, line $i+1$ contains $L_i$ and $R_i$, both integers in the range $1\ldots N$, with $L_i

On line $i$, output the ID of the $i$-th element (from left to right) in the cow sequence after the instruction sequence has been executed $K$ times.

#### Sample Explanation: Initially, the cows are ordered from left to right as [$1,2,3,4,5,6,7$]. After the first step of this process, the order becomes [$1,5,4,3,2,6,7$]. After the second step of this process, the order becomes [$1,5,7,6,2,3,4$]. Repeating these two steps one more time each gives the sample output. #### Subtasks: - Test case $2$ satisfies $N=K=100$. - Test cases $3$-$5$ satisfy $K\leq 10^3$. - Test cases $6$-$10$ have no additional constraints. Translated by ChatGPT 5