中间人

题目描述

注意:本题的输入格式特殊,且内存限制比平时更小。

有一张顶点为 $1, 2, \dots, N$ 的无向图,初始时没有边。

你需要处理对这个图进行的 $Q$ 个查询:

类型 1:1 u v

在顶点 $u$ 和 $v$ 之间添加一条边。

添加边之前,$u$ 和 $v$ 属于不同的连通分量(即图始终保持为森林)。

类型 2:2 u v

如果存在一个与 $u$ 和 $v$ 都相邻的顶点,输出该顶点的编号;否则输出 $0$。

由于图始终保持为森林,该查询的答案唯一确定。

查询以加密形式给出。

原始查询由三个整数 $A, B, C$ 定义,加密查询以三个整数 $a, b, c$ 给出。

设 $X_k$ 为第 $k$ 个类型 2 查询的答案。定义 $X_k = 0$($k = 0$)。

按如下方式从给定的 $a, b, c$ 还原 $A, B, C$:

设 $l$ 为本次查询之前给出的类型 2 查询的个数(不含本次查询)。使用:

$A = 1 + (((a \times (1+X_l)) \mod 998244353) \mod 2)$

$B = 1 + (((b \times (1+X_l)) \mod 998244353) \mod N)$

$C = 1 + (((c \times (1+X_l)) \mod 998244353) \mod N)$

输入格式

输入按以下格式从标准输入给出:

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

输出格式

设类型 2 查询的个数为 $k$。输出 $k$ 行。

第 $i$ 行输出第 $i$ 个类型 2 查询的答案。

样例

6 12
143209915 123840720 97293110
89822758 207184717 689046893
67757230 270920641 26993265
952858464 221010240 871605818
730183361 147726243 445163345
963432357 295317852 195433903
120904472 106195318 615645575
817920568 27584394 770578609
38727673 250957656 506822697
139174867 566158852 412971999
205467538 606353836 855642999
159292205 319166257 51234344

0
2
0
2
6
0
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$ 个查询的输入。

• 第一个查询是 2 1 3。没有与顶点 1 和顶点 3 都相邻的顶点,所以输出 0。
• 第二个查询是 1 2 6。在顶点 2 和 6 之间添加边。
• 第三个查询是 1 2 4。在顶点 2 和 4 之间添加边。
• 第四个查询是 1 1 3。在顶点 1 和 3 之间添加边。
• 第五个查询是 2 4 6。与顶点 4 和 6 都相邻的顶点是顶点 2。
• 第六个查询是 2 1 4。没有与顶点 1 和 4 都相邻的顶点,所以输出 0。
• 第七个查询是 1 5 6。在顶点 5 和 6 之间添加边。
• 第八个查询是 1 1 2。在顶点 1 和 2 之间添加边。
• 第九个查询是 2 1 4。与顶点 1 和 4 都相邻的顶点是顶点 2。
• 第十个查询是 2 2 5。与顶点 2 和 5 都相邻的顶点是顶点 6。
• 第十一个查询是 2 3 4。没有与顶点 3 和 4 都相邻的顶点,所以输出 0。
• 第十二个查询是 2 2 3。与顶点 2 和 3 都相邻的顶点是顶点 1。

2 1
377373366 41280240 33617925

输出可能为空。

数据范围

• 输入中的所有值均为整数。
• $2 \le N \le 10^5$
• $1 \le Q \le 10^5$
• $1 \le u \lt v \le N$
• $0 \le a,b,c \lt 998244353$