У Фафы есть массив A из n положительных чисел, определим функцию f(A) как . Он хочет обработать q запросов двух типов:
Обратите внимание, что запросы типа 1 не изменяют массив.
Первая строка содержит целое число n (3 ≤ n ≤ 105) — длину массива.
Вторая строка содержит n положительных целых чисел a1, a2, ..., an (0 < ai ≤ 109) — элементы массива.
Третья содержит целое число q (1 ≤ q ≤ 105) — количество запросов.
В следующих q строках описываются запросы, i-я из этих строк описывает i-й запрос и содержит четыре целых числа ti li ri xi .
Гарантируется, что есть хотя бы один запрос типа 1.
Для каждого запроса типа 1 выведите ответ на него.
5 1 1 1 1 1 5 1 2 4 1 2 2 3 1 2 4 4 2 2 3 4 1 1 3 3 2
2 8
5 1 2 3 4 5 4 1 2 4 2 2 2 4 1 2 3 4 1 1 2 4 2
6 10
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач