Le $N$ mucche di Farmer John ($1\le N\le 10^5$) sono in fila. Per ogni $1\le i\le N$, la mucca $i$ da sinistra ha etichetta $i$.

Farmer John ha inventato una nuova routine mattutina. Ha dato alle mucche $M$ coppie di interi $(L_1,R_1) \ldots (L_M, R_M)$, dove $1 \leq M \leq 100$, e chiede di ripetere esattamente $K$ volte ($1\le K\le 10^9$) questo processo di $M$ passi:

• Per ogni $i$ da $1$ a $M$:
• Le mucche attualmente nelle posizioni $L_i \ldots R_i$ da sinistra invertono il loro ordine.

Dopo esattamente $K$ ripetizioni, stampa l’etichetta della mucca $i$ da sinistra per ogni $1\le i\le N$.

Input

La prima riga contiene $N$, $M$ e $K$. Per ogni $1\le i\le M$, la riga $i+1$ contiene $L_i$ e $R_i$, interi nell’intervallo $1 \ldots N$ con $L_i < R_i$.

Output

Nella riga $i$, stampa l’elemento $i$ dell’array dopo aver eseguito la sequenza di istruzioni $K$ volte.

Esempi

Input 1

7 2 2
2 5
3 7

Output 1

1
2
4
3
5
7
6

Nota

Inizialmente l’ordine da sinistra a destra è $[1,2,3,4,5,6,7]$. Dopo il primo passo è $[1,5,4,3,2,6,7]$ e dopo il secondo $[1,5,7,6,2,3,4]$. Ripetere entrambi i passi una seconda volta dà l’output dell’esempio.

Sottoproblemi

• Il caso 2 soddisfa $N=K=100$.
• I casi 3-5 soddisfano $K\le 10^3$.
• I casi 6-10 non hanno vincoli aggiuntivi.

Autore del problema: Brian Dean