Problem
N cows (1 ≤ N ≤ 10
5) Farmer John stand in a row. The i-th cow on the left has label i (1 ≤ i ≤ N).
FD gave the cows M pairs of integers s (L
1,R
1)…(L
M,R
M), where 1 ≤ M≤ 100. Then he told the cows to repeat exactly K (1 ≤ K ≤ 10
9) times the process of M steps:
For every i from 1 to M:
The sequence of cows in positions Li…Ri on the left reverses their order.
Print the labels of all cows from left to right for each i, (1 ≤ i ≤ N) after the process is completed.
Input
The first line contains the numbers N, M, K. For each 1 ≤ i≤ M string i+1 contains L
i and R
i, two integers in the interval 1…N, where L
i<R
i.
Imprint
On the i-th line of the output, print the i-th element of the array after executing all instructions K times.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
7 2 2
25
3 7
|
1
2
4
3
5
7
6
|
Initially, the order of cows from left to right is [1,2,3,4,5,6,7]
After the first step of the process, the order will be [1,5,4,3,2,6,7]
After the second step of the process, the order will become [1,5,7,6,2,3,4].
Repeating both steps one more time we get the result shown in the output. |