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

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

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

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

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

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

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

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

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

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