$N$ коров Farmer John ($1\le N\le 10^5$) стоят в ряд. Для каждого $1\le i\le N$ у $i$-й коровы слева метка $i$.

Farmer John придумал новую утреннюю зарядку. Он дал коровам $M$ пар целых чисел $(L_1,R_1) \ldots (L_M, R_M)$, где $1 \leq M \leq 100$, и просит повторить следующий процесс из $M$ шагов ровно $K$ раз ($1\le K\le 10^9$):

• Для каждого $i$ от $1$ до $M$:
• Коровы, сейчас занимающие позиции $L_i \ldots R_i$ слева, меняют свой порядок на обратный.

После ровно $K$ повторений процесса выведите метку $i$-й коровы слева для каждого $1\le i\le N$.

Входные данные

Первая строка содержит $N$, $M$ и $K$. Для каждого $1\le i\le M$ строка $i+1$ содержит $L_i$ и $R_i$, целые числа в диапазоне $1 \ldots N$, причём $L_i < R_i$.

Выходные данные

В $i$-й строке выведите $i$-й элемент массива после выполнения последовательности инструкций $K$ раз.

Примеры

Входные данные 1

7 2 2
2 5
3 7

Выходные данные 1

1
2
4
3
5
7
6

Примечание

Изначально порядок слева направо равен $[1,2,3,4,5,6,7]$. После первого шага он равен $[1,5,4,3,2,6,7]$, после второго — $[1,5,7,6,2,3,4]$. Второе выполнение обоих шагов даёт вывод примера.

Подзадачи

• Тест 2 удовлетворяет $N=K=100$.
• Тесты 3-5 удовлетворяют $K\le 10^3$.
• В тестах 6-10 дополнительных ограничений нет.

Автор задачи: Brian Dean