AT_abc350_g.[ABC350G] Mediator

请注意特殊的输入格式。同时，请注意内存限制比通常更小。

有一个包含 $N$ 个顶点 $1,2,\dots,N$ 的无向图，初始时没有任何边。
请对该图处理以下 $Q$ 个查询。

1 $u$ $v$

类型 $1$：在顶点 $u$ 和顶点 $v$ 之间添加一条边。
在添加边之前，$u$ 和 $v$ 属于不同的连通分量（也就是说，图始终是一片森林）。

2 $u$ $v$

类型 $2$：如果存在同时与顶点 $u$ 和顶点 $v$ 相邻的顶点，则输出其编号，否则输出 $0$。
由于图始终是一片森林，可以证明对于该查询的答案是唯一的。

但是，上述查询是经过加密后给出的。
原始查询由 $3$ 个整数 $A,B,C$ 定义，基于此给出加密后的查询 $a,b,c$。
对于类型 $2$ 的查询，第 $k$ 个（从前往后数）查询的答案记为 $X_k$。此外，定义 $k=0$ 时 $X_k=0$。
请根据给定的 $a,b,c$ 按如下方式解密得到 $A,B,C$：

• 设在该查询之前已经给出的类型 $2$ 查询的个数为 $l$（不包括当前查询）。此时，按如下方式解密：
  • $A = 1 + (((a \times (1+X_l)) \bmod 998244353) \bmod 2)$
  • $B = 1 + (((b \times (1+X_l)) \bmod 998244353) \bmod N)$
  • $C = 1 + (((c \times (1+X_l)) \bmod 998244353) \bmod N)$

输入以如下格式从标准输入给出。
其中，$\rm{Query}_i$ 表示第 $i$ 个查询。

$N$ $Q$
$\rm{Query}_1$
$\rm{Query}_2$
$\vdots$
$\rm{Query}_Q$

设类型 $2$ 的查询总共有 $k$ 个，请输出 $k$ 行。
其中第 $i$ 行输出第 $i$ 个类型 $2$ 查询的答案。

限制

• 所有输入均为整数。
• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq u < v \leq N$
• $0 \leq a,b,c < 998244353$

样例解释 1

将所有查询解密后，输入如下：

6 12
2 1 3
1 2 6
1 2 4
1 1 3
2 4 6
2 1 4
1 5 6
1 1 2
2 1 4
2 2 5
2 3 4
2 2 3

对于该输入，图有 $6$ 个顶点，包含 $12$ 个查询。

• 第 $1$ 个查询为 2 1 3。
  顶点 $1$ 和顶点 $3$ 没有共同相邻的顶点，输出 $0$。
• 第 $2$ 个查询为 1 2 6。
  在顶点 $2$ 和顶点 $6$ 之间添加一条边。
• 第 $3$ 个查询为 1 2 4。
  在顶点 $2$ 和顶点 $4$ 之间添加一条边。
• 第 $4$ 个查询为 1 1 3。
  在顶点 $1$ 和顶点 $3$ 之间添加一条边。
• 第 $5$ 个查询为 2 4 6。
  顶点 $4$ 和顶点 $6$ 的共同相邻顶点为顶点 $2$。
• 第 $6$ 个查询为 2 1 4。
  顶点 $1$ 和顶点 $4$ 没有共同相邻顶点，输出 $0$。
• 第 $7$ 个查询为 1 5 6。
  在顶点 $5$ 和顶点 $6$ 之间添加一条边。
• 第 $8$ 个查询为 1 1 2。
  在顶点 $1$ 和顶点 $2$ 之间添加一条边。
• 第 $9$ 个查询为 2 1 4。
  顶点 $1$ 和顶点 $4$ 的共同相邻顶点为顶点 $2$。
• 第 $10$ 个查询为 2 2 5。
  顶点 $2$ 和顶点 $5$ 的共同相邻顶点为顶点 $6$。
• 第 $11$ 个查询为 2 3 4。
  顶点 $3$ 和顶点 $4$ 没有共同相邻顶点，输出 $0$。
• 第 $12$ 个查询为 2 2 3。
  顶点 $2$ 和顶点 $3$ 的共同相邻顶点为顶点 $1$。

样例解释 2

也可能出现输出为空的情况。

由 ChatGPT 4.1 翻译