Module: Fast exponentiation


Problem

5 /5


One-two-three-four-five cow change

Problem

N cows (1 ≤ N ≤ 105) 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 (L1,R1)…(LM,RM), where 1 ≤ M≤ 100. Then he told the cows to repeat exactly K (1 ≤ K ≤ 109) 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 Li and Ri, two integers in the interval 1…N, where Li<Ri.

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.