← 返回题目列表

Codeforces · 315/B

B. 塞雷贾和阵列

中文机器翻译题面 查看原题

Sereja 有一个数组,由 n 个整数 a1, a2, ..., an 组成。 Sereja 是一个活跃的男孩,所以他现在要完成 m 次手术。每个操作都将具有以下三种形式之一:

1. 使第 vi 个数组元素等于 xi。换句话说,执行赋值avi = xi。
2. 将每个数组元素增加 yi。换句话说,执行n次赋值ai = ai + yi (1 ≤ i ≤ n)。
3. 拿一张纸写出第 qi 个数组元素。即aqi元素。

帮助Sereja,完成他的所有操作。

输入

第一行包含整数 n, m (1 ≤ n, m ≤ 105)。第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 109) — 原始数组。

接下来m行描述操作,第i行描述第i个操作。第 i 行第一个数字是整数 ti (1 ≤ ti ≤ 3),表示操作类型。如果 ti = 1,则后面跟着两个整数 vi 和 xi,(1 ≤ vi ≤ n,1 ≤ xi ≤ 109)。如果 ti = 2,则其后为整数 yi (1 ≤ yi ≤ 104)。如果 ti = 3,则后面跟着整数 qi (1 ≤ qi ≤ n)。

输出

对于每个第三种类型的操作打印值aqi。按顺序打印值,其中相应的查询位于输入中。

示例

输入 #1

10 11
1 2 3 4 5 6 7 8 9 10
3 2
3 9
2 10
3 1
3 10
1 1 10
2 10
2 10
3 1
3 10
3 9

输出 #1

2
9
11
20
30
40
39