Своппер
Перед возвращением в штаб-квартиру Аазу и Скиву пришлось заполнить на местной таможне декларацию о доходах за время визита. Получилась довольно внушительная последовательность чисел. Обработка этой последовательности заняла весьма долгое время.
– Своппер кривой, – со знанием дела сказал таможенник.
– А что такое своппер? – спросил любопытный Скив.
Ааз объяснил, что своппер – это структура данных, которая умеет делать следующее:
взять отрезок чётной длины от x до y и поменять местами число x с x + 1, x + 2 с x + 3, и т.д;
посчитать сумму на произвольном отрезке от a до b.
Учитывая, что обсчёт может затянуться надолго, корпорация “МИФ” попросила Вас решить проблему со своппером и промоделировать ЭТО эффективно.
Входные данные
Состоит из одного или нескольких тестов. В первой строке каждого теста записаны длина последовательности n и количество операций m (1 ≤ n, m ≤ 100000). Вторая строка теста содержит n целых чисел, не превосходящих 10^6 по модулю - сама последовательность. Далее следует m строк - запросы в формате 1 x[i] y[i] - запрос первого типа, и 2 a[i] b[i] - запрос второго типа. Сумма всех n и m по всем входным данным не превосходит 200000. Входные данные завершаются строкой из двух нулей. Гарантируется, что x[i] < y[i], a[i] ≤ b[i].
Выходные данные
Для каждого теста выведите ответы на запросы второго типа, как показано в примере. Разделяйте ответы на тесты пустой строкой.