409766: GYM103736 G Ganyu Segment Tree

Ganyu just learns the persistent segment tree and decides to practice immediately. Since Paimon has become a master of the persistent segment tree, Ganyu asks her for help. Therefore Paimon gives her an easy problem to start:

The elements in the sequence have two states - locked and unlocked. If one element $$$a_i$$$ is locked, it cannot be modified, but the unlocked state has no effect. More formally, you can only modify elements that are in the unlocked state.

Given a sequence $$$a_1, a_2, \cdots, a_n$$$ of length $$$n$$$ with initial values of $$$1$$$ and states are unlocked.

Paimon will apply $$$m$$$ modifications to the sequence. There are $$$3$$$ types of modifications:

• flip $$$p$$$: change the state of the element $$$a_p$$$.
• mul $$$l$$$ $$$r$$$ $$$x$$$: for every element $$$a_i$$$ in the subarray $$$(a_l,a_{l+1}, \cdots,a_r)$$$, replace unlocked $$$a_i$$$ with $$$a_i \times x$$$.
• div $$$l$$$ $$$r$$$ $$$x$$$: for every element $$$a_i$$$ in the subarray $$$(a_l,a_{l+1}, \cdots,a_r)$$$, you should check if all of them(including elements in unlocked and locked states) are divisible by $$$x$$$. If it holds, replace unlocked $$$a_i$$$ with $$$a_i \div x$$$, otherwise do not perform the operation.

Please help Ganyu to check whether each div modification can be performed.

There is only one test case in each test file.

The first line of the input contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 10^5)$$$ indicating the length of the sequence, and the number of modifications.

Then the following $$$m$$$ lines indicate modifications. Each of them must be in one of the following forms.

• flip $$$p$$$
• mul $$$l$$$ $$$r$$$ $$$x$$$
• div $$$l$$$ $$$r$$$ $$$x$$$

All $$$p, l, r$$$ and $$$x$$$ mentioned in these $$$m$$$ lines satisfy $$$1\leq p \leq n$$$, $$$1 \leq l \leq r \leq n$$$ and $$$1 \leq x \leq 30$$$.

For each div modifications, print "YES" on the single line if all the elements in the subarray are divisible by $$$x$$$. Otherwise, print "NO".

You can print each letter in any case (upper or lower).

5 11
mul 1 5 18
div 2 3 6
div 1 2 9
flip 2
div 1 2 9
mul 2 2 3
div 1 2 9
div 2 3 3
flip 2
mul 2 2 3
div 1 2 9

YES
NO
NO
NO
YES
YES

Here is the explanation for the example:

• $$$[18, 18, 18, 18, 18]$$$
• $$$[18, 3, 3, 18, 18]$$$
• $$$[18, 3, 3, 18, 18]$$$, $$$a_2$$$ and $$$a_3$$$ are not divsiable by $$$9$$$
• $$$[18,$$$ 3$$$, 3, 18, 18]$$$, $$$a_2$$$ is locked
• $$$[18,$$$ 3$$$, 3, 18, 18]$$$, $$$a_2$$$ is not divsiable by $$$9$$$
• $$$[18,$$$ 3$$$, 3, 18, 18]$$$, $$$a_2$$$ is locked so you can't change its value
• $$$[18,$$$ 3$$$, 3, 18, 18]$$$, $$$a_2$$$ is not divsiable by $$$9$$$
• $$$[18,$$$ 3$$$, 1, 18, 18]$$$, $$$a_2$$$ and $$$a_3$$$ are divsiable by $$$3$$$ but $$$a_2$$$ is locked, so you only change $$$a_3$$$
• $$$[18, 3, 1, 18, 18]$$$, $$$a_2$$$ is unlocked
• $$$[18, 9, 1, 18, 18]$$$
• $$$[2, 1, 1, 18, 18]$$$