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。