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 翻译