Weighing Scale Operations

You are given n weight groups, numbered from \(1\) to \(n\). In the \(i\)th group, every weight has the same positive integer mass \(a_i\), and there are infinitely many weights available in each group.

There are \(q\) operations to perform. The operations are of the following types:

• I x v: Insert a new weight group with a single weight of mass \(v\) immediately after the \(x\)th group. If \(x = 0\), insert at the beginning.
• D x: Delete the \(x\)th weight group.
• A l r v: Add \(v\) to the mass of each weight in groups from \(l\) to \(r\) (inclusive).
• Q l r v: Query whether it is possible to measure an object of mass \(v\) using weights from groups \(l\) to \(r\). In this weighing process, you are allowed to use any number (including zero) of weights from each group and can place each weight on either side of the balance. A weighing is possible if and only if there exists a placement such that, when the object of mass \(v\) is placed on one pan, the scale balances.

An important observation is that using weights on both pans allows you to form any integer linear combination of the given weight masses. Hence, the weighing is possible if and only if the equation \[ x_1a_l + x_2a_{l+1} + \cdots + x_k a_r = v \quad \text{with } x_i \in \mathbb{Z} \] has a solution. By Bézout's identity, this is equivalent to \(\gcd(a_l, a_{l+1}, \dots, a_r)\) dividing \(v\). That is, the answer to a query is YES if \(\gcd(a_l, a_{l+1}, \dots, a_r)\) divides \(v\), and NO otherwise.

inputFormat

The first line contains two integers \(n\) and \(q\), representing the number of initial weight groups and the number of operations, respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the mass in each weight group.

The next \(q\) lines each contain an operation in one of the following formats:

• I x v
• D x
• A l r v
• Q l r v

Note that after an I or D operation, the numbering of the groups is automatically updated.

outputFormat

For each query of the form Q l r v, output a single line containing YES if a weighing is possible, or NO otherwise.

sample

3 4
2 4 6
Q 1 3 2
Q 1 3 3
A 2 3 1
Q 1 3 2

YES
NO
YES