Problem B
Låssmeden

Låssmeden Lårs har blivit ansvarig för att dela ut nycklar till låsen i Mattelandet. Landet har $N$ lås, som numreras $1,2,\ldots ,N$. Varje invånare har en egen nyckel som öppnar vissa (de som invånaren har rätt att öppna) av låsen i landet.

Varje gång en person flyttar till landet ger Lårs dem en nyckel som består av två tal $a,b$. Därefter kan personen öppna alla lås med nummer $m$ som uppfyller $m\equiv a \pmod{b}$¹. När en person flyttar från landet tar Lårs tillbaka deras nyckel.

Det finns tre typer av händelser som Lårs, i egenskap av låsansvarig, behöver hantera – svara på frågan om någon invånare kan öppna ett specifikt lås, någon som flyttar till landet och någon som flyttar från landet. Lårs ska på varje fråga om det finns någon invånare som kan öppna ett specifikt lås svara “ja” eller “nej”. Från början bor ingen i landet.

Indata

Den första raden innehåller två heltal $N,Q$, antalet lås och antalet händelser ($1\leq N,Q \leq 2\cdot 10^5$).

Därefter kommer $Q$ rader som är på någon av följande former:

• $1\enspace x$, en fråga om det finns någon invånare som kan öppna lås $x$ ($1\leq x \leq N$).

• $2\enspace a\enspace b$, någon flyttar till landet, och får nyckel $a,b$ som fungerar som beskrivet ovan ($0\leq a < b \leq N$).

• $3\enspace a\enspace b$, någon med nyckel $a,b$ flyttar från landet och Lårs tar tillbaka deras nyckel. Det är garanterat att en person med nyckel $a,b$ tidigare flyttat till landet ($0\leq a < b \leq N$).

Utdata

För varje fråga om någon kan låsa upp ett specifikt lås (första siffran är 1) ska du skriva ut “ja” om låset kan öppnas av någon invånare som just nu bor i landet, eller “nej” om låset inte kan öppnas.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall

I det första exemplet finns först ingen nyckel, därför kan inte lås $7$ öppnas. Därefter läggs en nyckel till som gör att alla heltal $m$ som har $m\equiv 1 (\mod 3)$ öppnar låsen, då kan lås $7$ öppnas. Slutligen tas nyckeln bort, då kan inte lås $7$ öppnas igen.

I det andra exemplet delas två likadana nycklar ut. När den ena av dem tas in igen kan fortfarande lås $7$ öppnas (alla likadana nycklar tas alltså inte in samtidigt).

10 5
1 7
2 1 3
1 7
3 1 3
1 7

nej
ja
nej

7 7
1 7
2 1 3
1 7
2 1 3
1 7
3 1 3
1 7

nej
ja
ja
ja

20 8
2 2 3
2 0 2
1 7
1 8
1 9
3 0 2
1 8
1 5

nej
ja
nej
ja
ja

200000 7
1 200000
2 2 3
1 200000
2 0 1
1 200000
3 2 3
1 200000

nej
ja
ja
ja