e-olymp
Задачі

Своппер

Своппер

Перед поверненням до штаб-квартири Аазу та Сківу довелось заповнити на місцевій таможні декларацію про доходи за час візиту. Получилась досить солідна послідовність чисел. Опрацювання цієї послідовності зайняла досить довгий час.

– Своппер кривий, - зі знанням справи сказав працівник таможні.

– А що таке своппер? - запитав допитливий Сків.

Ааз пояснив, що своппер - це структура даних, яка вміє робити наступне:

  • взяти відрізок парної довжини від x до y і поміняти місцями число x з x + 1, x + 2 з x + 3, і т.д;
  • порахувати суму на довільному відрізку від a до b.

Враховуючи, що підрахунок може затянутись надовго, корпорація “МІФ” попросила Вас вирішити проблему зі своппером і промоделювати ЦЕ ефективно.

Вхідні дані

Складається з одного або декількох тестів. У першому рядку кожного тесту записані довжина послідовності n та кількість операцій m (1n, m100000). Другий рядок теста містить n цілих чисел, які не перевищують 106 за модулем - сама послідовність. Далі йде m рядків - запити у форматі 1xiyi - запит першого типу, і 2aibi - запит другого типу. Сума всіх n та m по всім даним не перевищує 200000. Вхідні дані завершуються рядком з двох нулів. Гарантуєтсья, що xi < yi, aibi.

Вихідні дані

Для кожного тесту виведіть відповіді на запити другого типу, як показано в прикладі. Відокремлюйте відповіді на тести пустим рядком.

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
5 5
1 2 3 4 5
1 2 5
2 2 4
1 1 4
2 1 3
2 4 4
0 0
Вихідні дані #1
Swapper 1:
10
9
2
Автор В.Гольдштейн
Джерело Зимние сборы в Харькове 2010 День 2