Задача B. Переворачивания ≡

Условие

Учитель физкультуры школы с углубленным изучением предметов уже давно научился считать суммарный рост всех учеников, находящихся в ряду на позициях от l до r. Но дети играют с ним злую шутку. В некоторый момент дети на позициях с l по r меняются местами. Учитель заметил, что у детей не очень богатая фантазия, поэтому они всегда "переворачивают" этот отрезок, т. е. l меняется с r, l + 1 меняется с r − 1 и так далее. Но учитель решил не ругать детей за их хулиганство, а все равно посчитать суммарный рост на всех запланированных отрезках.

Формат входного файла

В первой строке записано два числа n и m (1 ≤ n, m ≤ 200 000) — количество детей в ряду и количество событий, произошедших за все время. Во второй строке задано n натуральных чисел — рост каждого школьника в порядке следования в ряду. Рост детей не превосходит 2 ⋅ 10⁵. Далее в m строках задано описание событий: три числа q, l, r в каждой строке (0 ≤ q ≤ 1, 1 ≤ l ≤ r ≤ n). Число q показывает тип события: 0 показывает необходимость посчитать и вывести суммарный рост школьников на отрезке [l, r]; 1 показывает то, что дети на отрезке [l, r] "перевернули" свой отрезок. Все числа во входном файле целые.

Формат выходного файла

Для каждого события типа 0 выведите единственное число на отдельной строке — ответ на этот запрос.

Примеры тестов

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

15
9
8
7
10