전화 요금제

"Dormi's Fone Service"는 CCOland의 유일한 전화 서비스 제공자이다. CCOland에는 1번부터 $N$번까지 번호가 매겨진 $N$개의 집이 있다. 각 전화선은 서로 다른 두 집을 잇고, 지금까지 존재했던 모든 전화선은 숲(forest)을 이룬다.

전화선에는 결함이 있어서 각 전화선은 단 하나의 시간 구간 동안만 존재한다. 두 집은 특정 시각에 한 집에서 다른 집까지 이어지는 전화선 경로가 있으면 그 시각에 서로 통화할 수 있다.

$Q$개의 질의를 처리해야 한다.

• 1 x y: 집 x와 y 사이에 전화선을 추가한다. 집 x와 y 사이에 전화선을 이전에 추가한 적이 없음이 보장된다.
• 2 x y: 집 x와 y 사이의 전화선을 제거한다. 현재 집 x와 y 사이에 전화선이 존재함이 보장된다.
• 3 t: 현재 질의부터 t개 전 질의까지의 구간 중 어느 한 시점에 서로 통화할 수 있는 서로 다른 집 쌍의 수를 구한다. $G_q$를 q번째 질의 후 CCOland의 상태, $G_0$를 어떤 질의도 적용하기 전의 상태라 하자. 이번 질의가 s번째 질의라면 $G_{s-t}, G_{s-t+1}, \dots, G_s$ 중 적어도 하나에서 연결된 집 쌍의 수를 센다.

첫 줄에는 $E$ ($E \in \{0, 1\}$)가 주어진다. $E = 0$이면 입력이 암호화되지 않은 것이고, $E = 1$이면 암호화된 것이다. 둘째 줄에는 집의 수 $N$과 질의의 수 $Q$가 공백으로 구분되어 주어진다. 이어서 $Q$개의 줄에 질의가 주어지며, 암호화 여부는 $E$에 따른다.

$q$번째 질의($1 \le q \le N$)에 대해 (복호화한 뒤) 1번과 2번 질의는 $1 \le x, y \le N$이고, 3번 질의는 $0 \le t \le q$가 보장된다.

암호화된 경우 인자 $x$, $y$, $t$는 실제 값과 가장 최근 3번 질의의 답을 비트 XOR한 값으로 주어진다. 아직 3번 질의가 없었다면 인자는 그대로이다.

각 3번 질의마다 답을 한 줄에 출력한다.