Задача 39514. One-two-three-four-five cow change

N cows (1 ≤ N ≤ 10⁵) 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₁,R₁)…(L_M,R_M), where 1 ≤ M≤ 100. Then he told the cows to repeat exactly K (1 ≤ K ≤ 10⁹) 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.