Polycarp has array of N integers a1, ..., aN. Polycarp makes experiments, he applies specific commands. There are M commands of three types. First one follows the form: 1 L R, it means we should decrease by 1 the numbers from array with indexes L, ..., R. Second one follows the form: 2 L R, it means we should increase by 1 the numbers from array with indexes L, ..., R. Third one follows the form: 3 L R a0 a1 a2 a3 a4, it means we should compute 
, for f(xi) = a0·xi4 + a1·xi3 + a2·xi2 + a3·xi1 + a4 and xi is number form array with index i. You should execute all given commands.
It is garantied that numbers in array always lesser than 201 and greater than - 201, and any sums from - 1018 to 1018.
The first line contains integer N — the number of integers in array (1 ≤ N ≤ 105). The first line contains a1, ..., aN — initial numbers in array. The third line contains integer M — the number of commands (1 ≤ M ≤ 105). M lines follow, each containing description of commands. Format is decribed above. 1 ≤ L ≤ R ≤ N, - 100 ≤ a0, a1, a2, a3, a4 ≤ 100.
Output result for each commands of third type in separated lines.
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
