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 (l1, r1), ..., (lm, rm). 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 li ... ri 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 ≤ 105), m (1 ≤m ≤ 100) and k (1 ≤ k ≤ 109). For each i (1 ≤ i ≤ m), line i + 1 line contains li and ri, both integers in the range 1...n, where li < ri.

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.