Problem Description

You have $n$ weight groups, numbered from $1$ to $n$. In the $i$-th weight group, all weights have the same positive integer mass $a_i$, and the number of weights in each weight group is unlimited.

There are $q$ operations:

• I x v: Insert a new weight group after the $x$-th weight group, where the mass of a single weight in this new group is $v$. When $x=0$, it means inserting at the very front.
• D x: Delete the $x$-th weight group.
• A l r v: Add $v$ to the mass of the weights in all weight groups from $l$ to $r$.
• Q l r v: Determine whether it is possible to measure mass $v$ using weights from weight groups $l$ to $r$. You may use any number of weights from each group, including zero.

For operations I and D, after the operation, the indices and the value of $n$ will change automatically.

A set of weights can measure mass $v$ if and only if there exists a way to place these weights on the two sides of the balance scale such that placing one object of mass $v$ on one side can make the scale balance.

Input Format

The first line contains $2$ integers $n,q$.

The second line contains $n$ integers, where the $i$-th integer is $a_i$.

The next $q$ lines each describe one operation.

Output Format

For each Q operation, output one line YES or NO, indicating whether mass $v$ can be measured.

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

Hint

[Sample Explanation]

For sample group $1$, in the end there are $5$ weight groups, with masses $5,18,9,16,2$ respectively. Put $1$ weight from weight group 1 on the left side of the balance, and put $1$ weight from weight group 3 on the right side, then you can measure mass $4$.

[Constraints]

This problem uses bundled testdata.

Let $m_1$ be the minimum value of $a_i$ and $v$ over all moments, and let $m_2$ be the maximum value of $a_i$ and $v$ over all moments.

• 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}$): There are no I operations and no D operations.
• Subtask #4 ($60\text{ pts}$): No special properties.

For $100\%$ of the data, $1\le n,q\le 10^5$, $1\le m_1\le m_2\le 10^{18}$. It is guaranteed that all operations are valid, and at any moment there is at least one weight group.

Translated by ChatGPT 5