$N$ krów Farmer John ($1\le N\le 10^5$) stoi w szeregu. Dla każdego $1\le i\le N$ krowa $i$ od lewej ma etykietę $i$.

Farmer John wymyślił nowe poranne ćwiczenia. Dał krowom $M$ par liczb całkowitych $(L_1,R_1) \ldots (L_M, R_M)$, gdzie $1 \leq M \leq 100$, i każe powtórzyć następujący proces z $M$ kroków dokładnie $K$ razy ($1\le K\le 10^9$):

• Dla każdego $i$ od $1$ do $M$:
• Krowy obecnie na pozycjach $L_i \ldots R_i$ od lewej odwracają swoją kolejność.

Po dokładnie $K$ powtórzeniach wypisz etykietę krowy $i$ od lewej dla każdego $1\le i\le N$.

Wejście

Pierwszy wiersz zawiera $N$, $M$ i $K$. Dla każdego $1\le i\le M$ wiersz $i+1$ zawiera $L_i$ i $R_i$, liczby całkowite w zakresie $1 \ldots N$, przy czym $L_i < R_i$.

Wyjście

W wierszu $i$ wypisz element $i$ tablicy po wykonaniu ciągu instrukcji $K$ razy.

Przykład

Wejście 1

7 2 2
2 5
3 7

Wyjście 1

1
2
4
3
5
7
6

Uwagi

Początkowa kolejność od lewej to $[1,2,3,4,5,6,7]$. Po pierwszym kroku to $[1,5,4,3,2,6,7]$, po drugim $[1,5,7,6,2,3,4]$. Drugie wykonanie obu kroków daje wyjście przykładu.

Podzadania

• Test 2 spełnia $N=K=100$.
• Testy 3-5 spełniają $K\le 10^3$.
• Testy 6-10 nie mają dodatkowych ograniczeń.

Autor zadania: Brian Dean