Description

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.

Input Format

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<R_i$.

Output Format

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.

7 2 2
2 5
3 7

1
2
4
3
5
7
6

Hint

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