N коров (1 ≤ N ≤ 10
5) Фермера Джона стоят в ряд. i-ая корова слева имеет метку i (1 ≤ i ≤ N).
ФД дал коровам M пар целых чисел s (L
1,R
1)…(L
M,R
M), где 1 ≤ M ≤ 100. Затем он сказал коровам повторить ровно K (1 ≤ K ≤ 10
9) раз процесс из M шагов:
Для каждого i от 1 до M:
Последовательность коров на позициях Li…Ri слева реверсивно меняют свой порядок.
Выведите метки всех коров слева направо для каждого i, (1 ≤ i ≤ N) после завершения описанного процесса.
Входные данные
Первая строка содержит числа N, M, K. Для каждого 1 ≤ i ≤ M строка i+1 содержит L
i и R
i, два целых числа в интервале 1…N, где L
i<R
i.
Выходные данные
На i-ой строке вывода, выведите i-ый элемент массива после выполнения всех инструкций K раз.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
7 2 2
2 5
3 7
|
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].
Повторив оба шага ещё раз получим результат, приведенный в выводе. |