题目描述

你有 $n$ 个砝码组，编号为 $1$ 至 $n$。对于第 $i$ 个砝码组中的砝码有共同的正整数质量 $a_i$，每个砝码组中的砝码数量无限。

其中，有 $q$ 次操作：

• I x v：在第 $x$ 个砝码组后新增一组单个砝码质量为 $v$ 的砝码组，当 $x=0$ 时表示在最前面新增；
• D x：删除第 $x$ 个砝码组；
• A l r v：把从 $l$ 到 $r$ 的所有砝码组中的砝码质量加 $v$；
• Q l r v：判断能否用从 $l$ 到 $r$ 的砝码组中的砝码，称出质量 $v$。每个砝码组中的砝码可以使用任意个，也可以不用。

对于操作 I 和 D，操作后编号以及 $n$ 的值自动变化。

称一些砝码可以称出质量 $v$，当且仅当存在将这些砝码分别放在天平两边的摆放方法，使得将 $1$ 个质量为 $v$ 的物体摆放在某边可以让天平平衡。

输入格式

第一行输入 $2$ 个整数 $n,q$。

第二行输入 $n$ 个整数，第 $i$ 个整数为 $a_i$。

接下来 $q$ 行，每行表示一个操作。

输出格式

对于每个 Q 操作，输出一行 YES 或者 NO，表示能否称出重量 $v$。

5 5
1 10 8 4 2
I 2 1
A 1 4 4
A 2 4 4
D 5
Q 1 4 4

YES

10 10
2 2 1 4 2 10 8 7 10 6
Q 5 6 1
Q 5 7 7
I 5 1
Q 4 5 3
Q 2 9 2
A 3 5 1
Q 7 8 5
D 7
A 3 9 7
Q 3 7 6

NO
NO
NO
YES
NO
YES

提示

【样例解释】

对于样例组 $1$，最后有 $5$ 个中的砝码组，质量分别为 $5,18,9,16,2$。在天平左边放上 $1$ 个砝码组一中的砝码，右边放上 $1$ 个砝码组三的砝码，即可称出质量 $4$。

【数据范围】

本题采用捆绑测试。

记 $m_1$ 为所有时刻中 $a_i$ 与 $v$ 的最小值，$m_2$ 为所有时刻中 $a_i$ 与 $v$ 的最大值。

• Subtask #1（$5\text{ pts}$）：$1\le n,q\le 10$，$1\le m_1\le m_2 \le50$。
• Subtask #2（$15\text{ pts}$）：$1\le n,q\le 4\times10^2$。
• Subtask #3（$20\text{ pts}$）：没有操作 I 与操作 D。
• Subtask #4（$60\text{ pts}$）：无特殊性质。

对于 $100\%$ 的数据，$1\le n,q\le 10^5$，$1\le m_1\le m_2\le 10^{18}$，保证所有操作合法，且任意时刻至少存在一个砝码组。