Республиканская олимпиада по информатике, 2012 год, 9 класс

(Простая задача)

Ограничение по времени:

2 секунды

Ограничение по памяти:

64 мегабайта

Имеется массив из $N$ целых чисел. Могут поступать следующие запросы:
    S a b — записать в ячейку с номером $a$ значение $b$ $(1 \le a \le N,$ |b| \le 10^6).$
    R l r — перевернуть подмассив с позиции $l$ до позиции $r$ $(1 \le l \le r \le N).$
    Q l r — вывести сумму элементов с позиции $l$ до позиции $r$ $(1 \le l \le r \le N).$

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

В первой строке входного файла одно целое число $N$ $(1 \le N \le 100000.)$ В следующей строке даны $N$ чисел, каждое из которых по абсолютному значению не превышает $10^6.$ В следующей строке дается одно целое число $M$ — количество запросов $(1 \le M \le 100000).$ В следующих $M$ строках заданы запросы в том виде, в каком они описаны в условии.

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

Для каждого запроса, начинающегося с $Q,$ выведите одну строку — ответ на этот запрос.

Примеры:

Вход

4
1 2 3 4
4
Q 1 3
R 2 4
S 1 4
Q 1 3

Ответ

6
11

Замечание

В не менее $40\%$ тестов $N, M \le 1000.$