У Поликарпа есть массив из N целых чисел a1, ..., aN. Над этим массивом Поликарп проводит опыты, а именно, применяет к нему некоторый набор операций. Всего операций M. Есть три типа операций. Первый тип задается строкой вида: 1 L R — это означает уменьшить числа в массиве на позициях L, ..., R на 1. Второй тип выглядит так: 2 L R — это означает увеличить числа в массиве на позициях L, ..., R на 1. Третий и последний тип выглядит как 3 L R a0 a1 a2 a3 a4. Он означает: вычислите 
, где f(xi) = a0·xi4 + a1·xi3 + a2·xi2 + a3·xi1 + a4 и xi — число в массиве на позиции i. Вам необходимо последовательно выполнить заданный набор операций.
Гарантируется, что в любой момент времени числа в массиве не превышают по модулю 200. Все значения сумм не превышают по модулю 1018.
В первой строке находится целое число N — количество чисел в массиве. 1 ≤ N ≤ 105.
Во второй строке находится N целых чисел — начальное содержимое массива.
В третьей строке находится целое число M — количество операций. 1 ≤ M ≤ 105.
В следующих M строках находятся описания операций. Формат для них указан выше. 1 ≤ L ≤ R ≤ N, - 100 ≤ a0, a1, a2, a3, a4 ≤ 100.
Для каждой операции третьего типа необходимо вывести в отдельных строках полученные значения.
5
1 2 3 4 5
7
3 1 5 0 0 0 0 1
3 1 5 0 0 0 1 0
3 1 5 0 0 1 0 0
3 1 5 0 1 0 0 0
3 1 5 1 0 0 0 0
1 1 5
3 1 5 1 0 0 0 0
5
15
55
225
979
354
5
1 2 3 4 5
5
1 1 5
1 1 5
1 1 5
3 1 5 0 1 0 1 0
3 1 5 1 0 1 0 5
0
69
