Своппер
Перед поверненням до штаб-квартири Аазу та Сківу довелось заповнити на місцевій таможні декларацію про доходи за час візиту. Получилась досить солідна послідовність чисел. Опрацювання цієї послідовності зайняла досить довгий час.
– Своппер кривий, - зі знанням справи сказав працівник таможні.
– А що таке своппер? - запитав допитливий Сків.
Ааз пояснив, що своппер - це структура даних, яка вміє робити наступне:
взяти відрізок парної довжини від 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].
Вихідні дані
Для кожного тесту виведіть відповіді на запити другого типу, як показано в прикладі. Відокремлюйте відповіді на тести пустим рядком.