As $N$ vacas de Farmer John ($1\le N\le 10^5$) estão numa fila. Para cada $1\le i\le N$, a $i$-ésima vaca a contar da esquerda tem rótulo $i$.

Farmer John inventou uma nova rotina matinal. Deu às vacas $M$ pares de inteiros $(L_1,R_1) \ldots (L_M, R_M)$, com $1 \leq M \leq 100$, e pede que repitam exatamente $K$ vezes ($1\le K\le 10^9$) este processo de $M$ passos:

• Para cada $i$ de $1$ a $M$:
• As vacas atualmente nas posições $L_i \ldots R_i$ da esquerda invertem a sua ordem.

Após exatamente $K$ repetições, imprima o rótulo da $i$-ésima vaca da esquerda para cada $1\le i\le N$.

Entrada

A primeira linha contém $N$, $M$ e $K$. Para cada $1\le i\le M$, a linha $i+1$ contém $L_i$ e $R_i$, inteiros no intervalo $1 \ldots N$, com $L_i < R_i$.

Saída

Na $i$-ésima linha, imprima o $i$-ésimo elemento do vetor após executar a sequência de instruções $K$ vezes.

Exemplos

Entrada 1

7 2 2
2 5
3 7

Saída 1

1
2
4
3
5
7
6

Nota

Inicialmente, a ordem da esquerda para a direita é $[1,2,3,4,5,6,7]$. Após o primeiro passo é $[1,5,4,3,2,6,7]$ e após o segundo, $[1,5,7,6,2,3,4]$. Repetir os dois passos uma segunda vez dá a saída do exemplo.

Subtarefas

• O teste 2 satisfaz $N=K=100$.
• Os testes 3-5 satisfazem $K\le 10^3$.
• Os testes 6-10 não têm restrições adicionais.

Autor do problema: Brian Dean