Description

给出一个长度为 $n$ 的序列 $a$，每次对序列进行一下的某一个操作。

Input Format

第一行两个整数 $n,q$ 表示序列长度和操作个数。
接下来一行 $n$ 个数，表示序列 $a$。
接下来 $q$ 行表示操作，其格式见题目描述。

Output Format

见题目描述。

Sample

样例输入

5 2
1 2 3 4 5
2 1 3
1 1 5

样例输出

12

样例解释

修改操作后序列为：1 1 1 4 5。

Hint

对于所有的数据，保证 $a_i$ 在 $\texttt{unsigned int}$ 范围内。