C. Маленький Артёмка и Танцы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маленький Артёмка очень любит танцевать. Особенно ему нравится танцевать руэду — кубинский танец, в котором все пары стоят по кругу.

Более детально: во время исполнения руэды n пар из мальчиков и девочек стоят по кругу. Изначально мальчик под номером 1 танцует с девочкой под номером 1, мальчик под номером 2 танцует с девочкой под номером 2 и так далее. Девочки пронумерованы в порядке по часовой стрелке. Во время танца громко объявляются различные команды, и все пары должны одновременно их исполнить, при этом мальчики могут в результате выполнения команд перемещаться вдоль круга, а девушки всегда стоят на своих изначальных местах. В данной задаче мы рассматриваем команды двух видов:

  1. Объявляется число x и направление, после чего все мальчики смещаются на x девушек в соответствующем направлении.
  2. Партнёры, которые танцуют с девушками с чётными индексами, меняются местами с партнёрами, которые танцуют с девушками с нечётными индексами, то есть тот, кто танцевал с девушкой 1, переходит к девушке номер 2, тот, кто танцевал с девушкой номер 2, переходит к девушке номер 1, тот, кто танцевал с девушкой номер 3, переходит к девушке номер 4 и так далее. Гарантируется, что n всегда чётно.

Ваша задача — определить конечное положение мальчиков после выполнения всех команд.

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

В первой строке входных данных записаны числа n и q (2 ≤ n ≤ 1 000 000, 1 ≤ q ≤ 2 000 000) — количество пар и количество выполненных команд соответственно. Гарантируется, что n чётно.

В следующих строках даны танцевальные команды в порядке их выполнения. Каждая команда начинается с целого числа, означающего ее тип, — 1 или 2. Команда первого типа является числом x ( - n ≤ x ≤ n), где 0 ≤ x ≤ n означает, что все мальчики переходят на x девушек в направлении по часовой стрелке, а x < 0 означает переход на  - x в направлении против часовой стрелки. Для команды второго типа нет дополнительных входных данных.

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

Выведите n чисел, i-е из которых означает номер мальчика, с которым танцует девушка номер i после выполнения всех команд.

Примеры
Входные данные
6 3
1 2
2
1 2
Выходные данные
4 3 6 5 2 1
Входные данные
2 3
1 1
2
1 -2
Выходные данные
1 2
Входные данные
4 2
2
1 3
Выходные данные
1 4 3 2