题目描述

古明地恋(koishi)和仙人掌(cactus)是好朋友。

恋恋种了许多棵仙人掌。这些仙人掌可以看成一个无向图，其中每条边最多属于一个简单环。这些仙人掌是动态的，会不断地长出新的无向边。仙人掌上的每条边都有一个权值，一条路径的权值为路径上所有边权的乘积。恋恋会给出一系列询问，每次询问给出两个点$u,v$，她想知道如果等概率随机选择一条$u$到$v$的简单路径（经过每个点最多一次），这条路径的期望权值是多少。如果并不存在$u$到$v$的简单路径，则这次询问的答案为$0$。答案对998244353取模。

注意在仙人掌的生长过程中，可能会长出破坏仙人掌性质的无向边，这时候恋恋会把这条不合法的新边剪掉。自环被认为是合法的，且不会对答案造成影响（因为没有任何简单路径会包含自环）。她也希望你能帮她判断出每条边的加入是否合法。

输入格式

第一行包含三个整数：$n,m,online$，分别表示无向图的点数，发生事件的总数，以及是否强制在线。
接下来$m$行中，每行第一个数$t$表示操作类型：
当$t=1$时，该事件为加边事件，接下来会有三个整数$u,v,w$，表示这条边的两个端点及边权。当$online=1$时，真实的$u,v$值为$u'=(u+lastans)\%n+1,v'=(v+lastans)\%n+1$，其中$lastans$为上一次询问事件的答案（初始为$0$）。
当$t=2$时，该事件为询问事件，接下来会有两个整数$u,v$，表示询问给出的两个点。当$online=1$时，真实的$u,v$值为$u'=(u+lastans)\%n+1,v'=(v+lastans)\%n+1$，其中$lastans$为上一次询问事件的答案（初始为$0$）。

输出格式

输出包含$m$行，对应$m$次事件：
如果事件为加边事件，输出"1"或"0"表示新边的加入是否合法（"1"表示合法，"0"表示非法）。
如果事件为询问事件，输出这次询问的答案对998244353取模的结果。

3 6 0
1 1 2 2
2 1 2
1 2 3 2
1 1 3 2
2 1 2
1 1 2 3

1
2
1
1
3
0

数据范围与提示

对于20%的数据，$n\leq1000,m\leq2000$
对于另20%的数据，满足任意时刻图中不会出现环
对于另20%的数据，满足所有询问操作都在最后一次加边事件之后
对于另20%的数据，$online=0$
对于100%的数据，$n\leq10^5,m\leq2*10^5,0\leq online\leq1,1\leq u,v\leq n,1\leq w<998244353$

题目来源：全是水题的GD省选模拟赛 by zjt