Farmer Johns $N$ Kühe ($1\le N\le 10^5$) stehen in einer Reihe. Für jedes $1\le i\le N$ trägt die $i$-te Kuh von links die Nummer $i$.

Farmer John hat eine neue Morgengymnastik erfunden. Er gibt den Kühen $M$ Paare ganzer Zahlen $(L_1,R_1) \ldots (L_M, R_M)$ mit $1 \leq M \leq 100$ und fordert sie auf, folgenden Prozess mit $M$ Schritten genau $K$ Mal ($1\le K\le 10^9$) zu wiederholen:

• Für jedes $i$ von $1$ bis $M$:
• Die Kühe, die sich gerade auf den Positionen $L_i \ldots R_i$ von links befinden, kehren ihre Reihenfolge um.

Gib nach genau $K$ Wiederholungen für jedes $1\le i\le N$ die Nummer der $i$-ten Kuh von links aus.

Eingabe

Die erste Zeile enthält $N$, $M$ und $K$. Für jedes $1\le i\le M$ enthält Zeile $i+1$ die ganzen Zahlen $L_i$ und $R_i$ im Bereich $1 \ldots N$ mit $L_i < R_i$.

Ausgabe

Gib in der $i$-ten Zeile das $i$-te Arrayelement nach $K$ Ausführungen der Anweisungsfolge aus.

Beispiele

Eingabe 1

7 2 2
2 5
3 7

Ausgabe 1

1
2
4
3
5
7
6

Hinweis

Anfangs lautet die Reihenfolge von links nach rechts $[1,2,3,4,5,6,7]$. Nach dem ersten Schritt lautet sie $[1,5,4,3,2,6,7]$, nach dem zweiten $[1,5,7,6,2,3,4]$. Eine zweite Ausführung beider Schritte ergibt die Beispielausgabe.

Teilaufgaben

• Testfall 2 erfüllt $N=K=100$.
• Testfälle 3-5 erfüllen $K\le 10^3$.
• Für Testfälle 6-10 gelten keine zusätzlichen Einschränkungen.

Autor der Aufgabe: Brian Dean