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

Автор:Жюри всероссийских зимних сборов школьников 2007-2008   Ограничение времени:5 сек
Входной файл:reverse.in   Ограничение памяти:64 Мб
Выходной файл:reverse.out  
Максимальный балл:100  

Условие

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

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

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

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

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

Ограничения

1 ≤ n, m ≤ 2 ⋅ 105

Рост детей не превосходит 2 ⋅ 105.

0 ≤ q ≤ 1

1 ≤ l ≤ r ≤ n

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

№ Входной файл (reverse.in) Выходной файл (reverse.out)
1 
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
0.038s 0.008s 15