Перестановка перестановки перестановки
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]. Повторение обоих шагов второй раз даст ответ.