P11373 "CZOI-R2" Balance Scale

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.

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.

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

**[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