Double Prefix Sum Queries

Given a sequence \(a_1, a_2, \dots, a_n\), the prefix sum is defined as \(S_i=\sum_{k=1}^{i}a_k\).

The preprefix sum (or double prefix sum) is obtained by taking the prefix sums as a new sequence and computing their prefix sums. Denote the result as \(SS_i\), i.e., \(SS_i=\sum_{j=1}^{i}S_j=\sum_{j=1}^{i}\sum_{k=1}^{j}a_k\).

You are given an array of length \(n\) and must execute \(q\) operations. There are two types of operations:

• Modify i x: Change \(a_i\) to \(x\).
• Query i: Output \(SS_i\), the preprefix sum up to index \(i\).

It can be shown that \(SS_i\) can be computed using the formula: \[ SS_i = (i+1)\cdot\left(\sum_{k=1}^{i}a_k\right) - \sum_{k=1}^{i}k\cdot a_k. \]

inputFormat

The first line contains two integers \(n\) and \(q\) --- the number of elements in the array and the number of operations.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the initial array.

The following \(q\) lines each contain an operation in one of the following formats:

• Modify i x
• Query i

outputFormat

For each Query i operation, output a single line containing the value of \(SS_i\).

sample

5 5
1 2 3 4 5
Query 3
Modify 2 10
Query 3
Modify 5 0
Query 5

10
26
62