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

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

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

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

• взяти відрізок парної довжини від 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.

Вихідні дані

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