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

Своппер кривий, — зі знанням справи сказав митник.

А що таке свопер? - Запитав цікавий Сків.

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

• Взяти відрізок парної довжини від \(𝑥\) до \(𝑦\) і поміняти місцями число \(𝑥\) з \(𝑥+1\), \(𝑥+2\) з \(𝑥+3\), і т.д.
• Порахувати суму чисел на довільному відрізку від \(𝑎\) до \(𝑏\).

Враховуючи, що облік може затягнутися надовго, корпорація «МІФ» попросила Вас вирішити проблему зі свопером та промоделювати ЦЕ ефективно.

Формат вхідних даних

У вхідному файлі задано один або кілька тестів.

У першому рядку кожного тесту записано число \(𝑁\) — довжина послідовності та число \(𝑀\) — число операцій (\(1≤𝑁,𝑀≤100000\)).

У другому рядку тесту міститься \(N\) цілих чисел, що не перевищують \(10^6\) за модулем — сама послідовність.

Далі йдуть \(M\) рядків - запити у форматі 1 \(𝑥_𝑖\) \(𝑦_𝑖\) - запит першого типу, і 2 \(𝑎_𝑖\) \(𝑏_𝑖\) - запит другого типу. Сума всіх \(𝑁\) і \(𝑀\) по всьому файлу не перевищує 200 000 . Файл завершується рядком із двох нулів. Гарантується, що \(𝑥_𝑖≤𝑦_𝑖\) , а \(𝑎_𝑖≤𝑏_𝑖\) .

Формат вихідних даних

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

Приклад вхідних даних

5 5
1 2 3 4 5
1 2 5
2 2 4
1 1 4
2 1 3
2 4 4
5 5
1 2 3 4 5
1 2 5
2 2 4
1 1 4
2 1 3
2 4 4
0 0

Приклад вихідних даних

Swapper 1:
10
9
2

Swapper 2:
10
9
2