Farmer John's NN cows (1≤N≤1051≤N≤105) are standing in a line. The iith cow from the left has label ii for each 1≤i≤N1≤i≤N.Farmer John has come up with a new morning exercise routine for the cows. He has given the cows MM pairs of integers (L1,R1**)…(LM**,RM**)(L1,R1)…(LM,RM), where 1≤M≤1001≤M≤100. He then tells the cows to repeat the following MM-step process exactly KK (1≤K≤10**91≤K≤109) times:

• For each ii from 11 to MM:
  • The sequence of cows currently in positions Li**…Ri**Li…Ri from the left reverse their order.

After the cows have repeated this process exactly KK times, please output the label of the iith cow from the left for each 1≤i≤N1≤i≤N.

SCORING:

• Test case 2 satisfies N=K=100N=K=100.
• Test cases 3-5 satisfy K≤103K≤103.
• Test cases 6-10 satisfy no additional constraints.

INPUT FORMAT (file swap.in):

The first line contains NN, MM, and KK. For each 1≤i≤M1≤i≤M, line i+1i+1 line contains LiLi and RiRi, both integers in the range 1…N1…N, where Li**<Ri**Li<Ri.

OUTPUT FORMAT (file swap.out):

On the iith line of output, print the iith element of the array after the instruction string has been executed KK times.

SAMPLE INPUT:

7 2 2
2 5
3 7

SAMPLE OUTPUT:

1
2
4
3
5
7
6

Initially, the order of the cows is [1,2,3,4,5,6,7][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][1,5,4,3,2,6,7]. After the second step of the process, the order is [1,5,7,6,2,3,4][1,5,7,6,2,3,4]. Repeating both steps a second time yields the output of the sample.