자물쇠공

자물쇠공 Lårs는 Mattelandet의 자물쇠에 열쇠를 나눠 주는 일을 맡게 되었다. 나라에는 $N$개의 자물쇠가 있고, 각각 $1,2,\ldots,N$으로 번호가 매겨져 있다. 주민마다 자기 열쇠를 가지고 있고, 그 열쇠로 나라의 자물쇠 중 일부(자기가 열 권한이 있는 자물쇠)를 열 수 있다.

누군가 나라로 이사 올 때마다 Lårs는 두 수 $a,b$로 이루어진 열쇠를 준다. 그러면 그 사람은 $m\equiv a \pmod{b}$를 만족하는 번호 $m$의 모든 자물쇠를 열 수 있다. (여기서 $\equiv$는 합동을 나타낸다. 두 수 $x,y$가 법 $n$에 대해 합동이라는 것은 $x\equiv y \pmod{n}$으로 쓰고, $n|(x-y)$ 즉 $x-y$가 $n$으로 나누어떨어진다는 뜻이다. 이는 $x$와 $y$를 $n$으로 나눈 나머지가 같다는 것과 같다. 대부분의 프로그래밍 언어에서는 $x\%n==y\%n$으로 쓸 수 있다.) 누군가 나라에서 이사 나가면 Lårs는 그 열쇠를 회수한다.

자물쇠 담당자로서 Lårs가 처리해야 하는 사건은 세 가지다. 어떤 주민이 특정 자물쇠를 열 수 있는지 묻는 질문, 누군가 나라로 이사 오는 일, 누군가 나라에서 이사 나가는 일이다. 어떤 주민이 특정 자물쇠를 열 수 있는지 묻는 질문마다 Lårs는 "ja" 또는 "nej"로 답해야 한다. 처음에는 아무도 나라에 살지 않는다.

첫째 줄에는 두 정수 $N,Q$가 주어진다. 이는 자물쇠의 수와 사건의 수다 ($1\leq N,Q \leq 2\cdot 10^5$).

이어서 $Q$개의 줄이 다음 중 한 형태로 주어진다.

• $1\enspace x$: 어떤 주민이 자물쇠 $x$를 열 수 있는지 묻는 질문이다 ($1\leq x \leq N$).
• $2\enspace a\enspace b$: 누군가 나라로 이사 오고, 위에서 설명한 대로 동작하는 열쇠 $a,b$를 받는다 ($0\leq a < b \leq N$).
• $3\enspace a\enspace b$: 열쇠 $a,b$를 가진 사람이 나라에서 이사 나가고 Lårs가 그 열쇠를 회수한다. 열쇠 $a,b$를 가진 사람이 이전에 나라로 이사 온 적이 있음이 보장된다 ($0\leq a < b \leq N$).

어떤 주민이 특정 자물쇠를 열 수 있는지 묻는 질문(첫 번째 수가 1인 줄)마다, 현재 나라에 사는 주민 중 그 자물쇠를 열 수 있는 사람이 있으면 "ja"를, 없으면 "nej"를 출력한다.

첫 번째 예시에서는 처음에 열쇠가 하나도 없으므로 자물쇠 $7$을 열 수 없다. 그다음 $m\equiv 1 (\mod 3)$인 모든 정수 $m$이 자물쇠를 열게 하는 열쇠가 추가되므로 자물쇠 $7$을 열 수 있다. 마지막으로 열쇠가 제거되면 자물쇠 $7$을 다시 열 수 없다.

두 번째 예시에서는 똑같은 열쇠가 두 개 발급된다. 그중 하나를 다시 회수해도 자물쇠 $7$은 여전히 열 수 있다(즉, 똑같은 열쇠를 한꺼번에 모두 회수하지는 않는다).