Las $N$ vacas de Farmer John ($1\le N\le 10^5$) están en fila. Para cada $1\le i\le N$, la vaca $i$ desde la izquierda tiene etiqueta $i$.

Farmer John ha inventado una nueva rutina matinal. Ha dado a las vacas $M$ pares de enteros $(L_1,R_1) \ldots (L_M, R_M)$, donde $1 \leq M \leq 100$, y les pide repetir exactamente $K$ veces ($1\le K\le 10^9$) este proceso de $M$ pasos:

• Para cada $i$ de $1$ a $M$:
• Las vacas actualmente en las posiciones $L_i \ldots R_i$ desde la izquierda invierten su orden.

Tras exactamente $K$ repeticiones, imprime la etiqueta de la vaca $i$ desde la izquierda para cada $1\le i\le N$.

Entrada

La primera línea contiene $N$, $M$ y $K$. Para cada $1\le i\le M$, la línea $i+1$ contiene $L_i$ y $R_i$, enteros en el rango $1 \ldots N$, con $L_i < R_i$.

Salida

En la línea $i$, imprime el elemento $i$ del arreglo tras ejecutar la secuencia de instrucciones $K$ veces.

Ejemplos

Entrada 1

7 2 2
2 5
3 7

Salida 1

1
2
4
3
5
7
6

Nota

Inicialmente, el orden de izquierda a derecha es $[1,2,3,4,5,6,7]$. Tras el primer paso es $[1,5,4,3,2,6,7]$ y tras el segundo, $[1,5,7,6,2,3,4]$. Repetir ambos pasos una segunda vez produce la salida del ejemplo.

Subtareas

• El caso 2 cumple $N=K=100$.
• Los casos 3-5 cumplen $K\le 10^3$.
• Los casos 6-10 no tienen restricciones adicionales.

Autor del problema: Brian Dean