Swapity Swapity Swap
Farmer John's n cows are standing in a line. The i-th cow from the left has label i ( 1 ≤ i ≤ n). Farmer John has come up with a new morning exercise routine for the cows. He has given the cows m pairs of integers (l[1], r[1]), ..., (l[m], r[m]). He then tells the cows to repeat the following m-step process exactly k times:
For each i from 1 to m:
The sequence of cows currently in positions
l[i]...r[i]from the left reverse their order.
After the cows have repeated this process exactly k times, print the label of the i-th cow from the left for each i (1 ≤ i ≤ n).
Input
The first line contains n (1 ≤ n ≤ 10^5), m (1 ≤m ≤ 100) and k (1 ≤ k ≤ 10^9). For each i (1 ≤ i ≤ m), line i + 1 line contains l[i] and r[i], both integers in the range 1...n, where l[i] < r[i].
Output
On the i-th line print the i-th element of the array after the instruction string has been executed k times.
Example
Initially, the order of the cows is [1, 2, 3, 4, 5, 6, 7] from left to right. After the first step of the process, the order is [1, 5, 4, 3, 2, 6, 7]. After the second step of the process, the order is [1, 5, 7, 6, 2, 3, 4]. Repeating both steps a second time yields the output of the sample.