Problem Description

The prefix sum is defined as $S_i=\sum_{k=1}^i a_k$.

The preprefix sum (preprefix sum) takes $S_i$ as the original sequence and computes the prefix sum again. Let the $i$-th value of this second prefix sum be $SS_i$.

Given a sequence $a_1, a_2, \cdots, a_n$ of length $n$, there are two types of operations:

1. Modify i x: Change $a_i$ to $x$.
2. Query i: Query $SS_i$.

Input Format

The first line contains two integers $N, M$, representing the length of the sequence and the number of operations.
The next line contains $N$ numbers, the given sequence $a_1, a_2, \cdots, a_n$.
The next $M$ lines each contain one operation, with the format described above.

Output Format

For each query operation, output one line containing the value of $SS_i$ being queried.

5 3
1 2 3 4 5
Query 5
Modify 3 2
Query 5

35
32

Hint

Constraints: $1\le N,M\le 10^5$, and at any time $0\le A_i\le 10^5$.

Translated by ChatGPT 5