자물쇠공

자물쇠공 Lårs는 Mattelandet에 있는 자물쇠의 열쇠를 나누어 주는 일을 맡게 되었다. 이 나라에는 $N$개의 자물쇠가 있으며, 번호는 $1,2,\ldots,N$이다. 각 주민에게는 이 나라의 자물쇠 중 일부, 즉 그 주민에게 열 권한이 있는 자물쇠를 여는 자신만의 열쇠가 있다.

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

자물쇠 관리자인 Lårs가 처리해야 하는 사건에는 세 가지 유형이 있다. 어떤 주민이 특정 자물쇠를 열 수 있는지 묻는 질문, 누군가가 이 나라로 이주하는 사건, 누군가가 이 나라를 떠나는 사건이다. Lårs는 어떤 주민이 특정 자물쇠를 열 수 있는지를 묻는 각 질문에 ja'' 또는 nej''라고 답해야 한다. 처음에는 이 나라에 아무도 살지 않는다.

채점

제출한 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$25$| 누군가가 자물쇠를 열려고 시도하는 사건의 수는 $\leq 20$이다.

$2$ |$30$| 아무도 이 나라를 떠나지 않으며, 모두 서로 다른 $b$를 선택한다.

$3$ |$45$| 추가 제한이 없다.

첫째 줄에 자물쇠의 수와 사건의 수를 나타내는 두 정수 $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$을 열 수 있다(즉, 동일한 열쇠가 모두 동시에 회수되지는 않는다).