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