← 返回题目列表

Codeforces · 679/E

E. 熊和 42 的坏力量

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

Limak 是一只熊,不擅长处理查询。所以,他要求你这样做。

我们说 42 的幂(数字 1, 42, 1764, ...)是不好的。其他数字都不错。

给定一个由 n 个好整数 t1, t2, ..., tn 组成的序列。您的任务是处理三种类型的 q 查询:

1. 1 i — 在单独的行中打印 ti。
2. 2 a b x — 对于 $$i \in [a,b]$$ 将 ti 设置为 x。保证 x 是一个好数。
3. 3 a b x — 对于 $$i \in [a,b]$$ 将 ti 增加 x。此后,当至少有一个 ti 出现问题时,请重复该过程。

您可以注意到,每次查询后,所有 ti 都很好。

输入

输入的第一行包含两个整数 n 和 q (1 ≤ n, q ≤ 100 000)——分别是 Limak 序列的大小和查询的数量。

输入的第二行包含 n 个整数 t1, t2, ..., tn (2 ≤ ti ≤ 109) - Limak 序列的初始元素。一切都很好。

然后是 q 行。其中第 i 个描述第 i 个查询。该行中的第一个数字是整数 typei (1 ≤ typei ≤ 3) — 查询的类型。至少有一个第一类型的查询,因此输出不会为空。

在第二类和第三类查询中,有 1 ≤ a ≤ b ≤ n。

在第二种类型的查询中,整数 x (2 ≤ x ≤ 109) 保证是好的。

在第三种类型的查询中,整数 x (1 ≤ x ≤ 109) 可能不好。

输出

对于第一种类型的每个查询,在单独的行中打印答案。

示例

输入 #1

6 12
40 1700 7 1672 4 1722
3 2 4 42
1 2
1 3
3 2 6 50
1 2
1 4
1 6
2 3 4 41
3 1 5 1
1 1
1 3
1 5

输出 #1

1742
49
1842
1814
1822
43
44
107

注意

查询 3 2 4 42 后,序列为 40, 1742, 49, 1714, 4, 1722。

查询 3 2 6 50 后,序列为 40, 1842, 149, 1814, 104, 1822。

查询 2 3 4 41 后,序列为 40, 1842, 41, 41, 104, 1822。

查询 3 1 5 1 后,序列为 43, 1845, 44, 44, 107, 1822。