eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Своппер

Своппер

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

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

– Своппер кривой, – со знанием дела сказал таможенник.

– А что такое своппер? – спросил любопытный Скив.

Ааз объяснил, что своппер – это структура данных, которая умеет делать следующее:

  • взять отрезок чётной длины от x до y и поменять местами число x с x + 1, x + 2 с x + 3, и т.д;

  • посчитать сумму на произвольном отрезке от a до b.

Учитывая, что обсчёт может затянуться надолго, корпорация “МИФ” попросила Вас решить проблему со своппером и промоделировать ЭТО эффективно.

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

Состоит из одного или нескольких тестов. В первой строке каждого теста записаны длина последовательности n и количество операций m (1n, m100000). Вторая строка теста содержит n целых чисел, не превосходящих 10^6 по модулю - сама последовательность. Далее следует m строк - запросы в формате 1x[i]y[i] - запрос первого типа, и 2a[i]b[i] - запрос второго типа. Сумма всех n и m по всем входным данным не превосходит 200000. Входные данные завершаются строкой из двух нулей. Гарантируется, что x[i] < y[i], a[i]b[i].

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

Для каждого теста выведите ответы на запросы второго типа, как показано в примере. Разделяйте ответы на тесты пустой строкой.

Пример

Входные данные #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