The Locksmith

The locksmith Lårs has been put in charge of handing out keys to the locks of Mattelandet. The country has $N$ locks, numbered $1,2,\ldots,N$. Every inhabitant has a key that opens certain locks in the country (those the inhabitant is allowed to open).

Whenever a person moves into the country, Lårs gives them a key consisting of two numbers $a,b$. The person can then open every lock with a number $m$ satisfying $m\equiv a \pmod{b}$. (Here $\equiv$ denotes congruence. Two numbers $x,y$ are said to be congruent modulo $n$, written $x\equiv y \pmod{n}$, if $n|(x-y)$, that is, $x-y$ is evenly divisible by $n$. This is the same as $x$ and $y$ having the same remainder when divided by $n$. In most programming languages it can be written as $x\%n==y\%n$.) When a person moves out of the country, Lårs takes back their key.

There are three types of events that Lårs, as the person in charge of locks, has to handle: answering the question of whether some inhabitant can open a specific lock, someone moving into the country, and someone moving out of the country. For every question about whether there is some inhabitant who can open a specific lock, Lårs must answer "ja" or "nej". Initially nobody lives in the country.

The first line contains two integers $N,Q$, the number of locks and the number of events ($1\leq N,Q \leq 2\cdot 10^5$).

Then come $Q$ lines, each in one of the following forms:

• $1\enspace x$, a question about whether there is some inhabitant who can open lock $x$ ($1\leq x \leq N$).
• $2\enspace a\enspace b$, someone moves into the country and receives key $a,b$ which works as described above ($0\leq a < b \leq N$).
• $3\enspace a\enspace b$, someone with key $a,b$ moves out of the country and Lårs takes back their key. It is guaranteed that a person with key $a,b$ has previously moved into the country ($0\leq a < b \leq N$).

For every question about whether someone can unlock a specific lock (lines whose first number is 1), print "ja" if the lock can be opened by some inhabitant currently living in the country, or "nej" if the lock cannot be opened.

In the first example there is initially no key, so lock $7$ cannot be opened. Then a key is added that makes every integer $m$ with $m\equiv 1 (\mod 3)$ open locks, so lock $7$ can be opened. Finally the key is removed, and lock $7$ can no longer be opened.

In the second example two identical keys are handed out. When one of them is taken back, lock $7$ can still be opened (that is, all identical keys are not taken back at the same time).