Перестановка перестановки перестановки
n корів Фермера Джона стоять у ряд. i-та корова зліва має мітку i ( 1 ≤ i ≤ n). Фермер Джон дав коровам m пар цілих чисел (l[1], r[1]), ..., (l[m], r[m]). Потім він попросив корів виконати рівно k разів операцію, що складається з m кроків:
Для кожного i від 1 до m:
Послідовність корів на позиціях
l[i]доr[i]зліва змінює свій порядок на зворотний.
Виведіть мітки всіх корів зліва направо для кожного i (1 ≤ i ≤ n) після завершення описаного процесу.
Вхідні дані
Перша стрічка містить числа n (1 ≤ n ≤ 10^5), m (1 ≤ m ≤ 100), k (1 ≤ k ≤ 10^9). Для кожного i (1 ≤ i ≤ m) стрічка i + 1 містить l[i] і r[i] (l[i] < r[i]) - два цілі числа в інтервалі [1, n].
Вихідні дані
В i-му рядку виведіть i-й елемент масиву після виконання всіх інструкцій k разів.
Приклад
Спочатку корови розташовані в такому порядку: [1, 2, 3, 4, 5, 6, 7] зліва направо. Після виконання першого кроку порядок буде таким: [1, 5, 4, 3, 2, 6, 7]. Після виконання другого кроку порядок буде таким: [1, 5, 7, 6, 2, 3, 4]. Повторення обох кроків вдруге дасть відповідь.