Les $N$ vaches de Farmer John ($1\le N\le 10^5$) sont en ligne. Pour chaque $1\le i\le N$, la $i$-ième vache depuis la gauche porte le numéro $i$.

Farmer John a inventé une nouvelle routine matinale. Il a donné aux vaches $M$ paires d’entiers $(L_1,R_1) \ldots (L_M, R_M)$, où $1 \leq M \leq 100$, puis leur demande de répéter exactement $K$ fois ($1\le K\le 10^9$) ce processus en $M$ étapes :

• Pour chaque $i$ de $1$ à $M$ :
• Les vaches actuellement aux positions $L_i \ldots R_i$ depuis la gauche inversent leur ordre.

Après exactement $K$ répétitions, affichez le numéro de la $i$-ième vache depuis la gauche pour chaque $1\le i\le N$.

Entrée

La première ligne contient $N$, $M$ et $K$. Pour chaque $1\le i\le M$, la ligne $i+1$ contient $L_i$ et $R_i$, deux entiers dans $1 \ldots N$ tels que $L_i < R_i$.

Sortie

Sur la $i$-ième ligne, affichez le $i$-ième élément du tableau après avoir exécuté la séquence d’instructions $K$ fois.

Exemples

Entrée 1

7 2 2
2 5
3 7

Sortie 1

1
2
4
3
5
7
6

Remarque

Initialement, l’ordre de gauche à droite est $[1,2,3,4,5,6,7]$. Après la première étape, il est $[1,5,4,3,2,6,7]$, puis $[1,5,7,6,2,3,4]$ après la deuxième. Répéter les deux étapes donne la sortie de l’exemple.

Sous-tâches

• Le test 2 satisfait $N=K=100$.
• Les tests 3-5 satisfont $K\le 10^3$.
• Les tests 6-10 n’ont pas de contraintes supplémentaires.

Auteur du problème : Brian Dean