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.
## Input
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
Output result for each commands of third type in separated lines.
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the length of the array.
Let $ A = (a_1, a_2, \dots, a_N) \in \mathbb{Z}^N $ be the initial array.
Let $ M \in \mathbb{Z}^+ $ be the number of commands.
Let $ \mathcal{C} = \{C_1, \dots, C_M\} $ be the sequence of commands, where each $ C_j $ is one of:
- Type 1: $ (1, L, R) $ — decrement $ a_i \leftarrow a_i - 1 $ for all $ i \in [L, R] $,
- Type 2: $ (2, L, R) $ — increment $ a_i \leftarrow a_i + 1 $ for all $ i \in [L, R] $,
- Type 3: $ (3, L, R, a_0, a_1, a_2, a_3, a_4) $ — compute $ \sum_{i=L}^{R} f(a_i) $, where $ f(x) = a_0 x^4 + a_1 x^3 + a_2 x^2 + a_3 x + a_4 $.
**Constraints**
1. $ 1 \le N \le 10^5 $
2. $ 1 \le M \le 10^5 $
3. For all $ i \in \{1, \dots, N\} $: $ -201 < a_i < 201 $
4. For all commands of Type 3: $ -100 \le a_0, a_1, a_2, a_3, a_4 \le 100 $
5. For all commands: $ 1 \le L \le R \le N $
6. All intermediate sums lie in $ [-10^{18}, 10^{18}] $
**Objective**
For each command $ C_j $ of Type 3, output:
$$
\sum_{i=L}^{R} \left( a_0 a_i^4 + a_1 a_i^3 + a_2 a_i^2 + a_3 a_i + a_4 \right)
$$