n коров Фермера Джона стоят в ряд. i-ая корова слева имеет метку i ( 1 ≤ i ≤ n). Фермер Джон дал коровам m пар целых чисел (l1, r1), ..., (lm, rm). Затем он сказал коровам повторить ровно k раз операцию из m шагов:

Для каждого i от 1 до m:

• Последовательность коров на позициях li .... ri слева реверсивно меняют свой порядок.

Выведите метки всех коров слева направо для каждого i, (1 ≤ i ≤ n) после завершения описанного процесса.

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

Первая строка содержит числа n (1 ≤ n ≤ 105), m (1 ≤ m ≤ 100), k (1 ≤ k ≤ 109). Для каждого i (1 ≤ i ≤ m) строка i + 1 содержит li и ri (li< ri) - два целых числа в интервале [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]. Повторение обоих шагов второй раз даст ответ.