你有一个数组 $$$a_1,a_2, \dots, a_n$$$。每个元素最初具有值 $$$0$$$ 和颜色 $$$1$$$。您还需要执行 $$$q$$$ 查询:
- 颜色 $$$l$$$ $$$r$$$ $$$c$$$:将元素 $$$a_l,a_{l+1},\cdots,a_r$$$ 的颜色更改为 $$$c$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le c \le n$$$)。
- 添加 $$$c$$$ $$$x$$$:将 $$$x$$$ 添加到颜色 $$$c$$$($$$1 \le c \le n$$$、$$$-10^9 \le x \le 10^9$$$)的所有元素 $$$a_i$$$ ($$$1 \le i \le n$$$) 的值。
- 查询$$$i$$$:打印$$$a_i$$$ ($$$1 \le i \le n$$$)。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n,q \le 10^6$$$) — 数组 $$$a$$$ 的长度以及必须执行的查询数量。
接下来的 $$$q$$$ 行包含以问题陈述中描述的形式给出的查询。
输出
在单独的行上打印第三类查询的答案。
示例
输入 #1
5 8 Color 2 4 2 Add 2 2 Query 3 Color 4 5 3 Color 2 2 3 Add 3 3 Query 2 Query 5
输出 #1
2 5 3
输入 #2
2 7 Add 1 7 Query 1 Add 2 4 Query 2 Color 1 1 1 Add 1 1 Query 2
输出 #2
7 7 8
注意
第一个样本测试解释如下。蓝色、红色和绿色分别代表颜色$$$1$$$、$$$2$$$ 和$$$3$$$。