Start: Jun, 19, 2019 19:00:00
6/19阿力的难题
End: Jun, 19, 2019 22:00:00
Time elapsed:
Time remaining:

阿力的困惑 1075

Time Limit:  2 Sec    Memory Limit:   256 MB
Submission:35     AC:7     Score:100


Description

阿力最近碰到了一点困惑,需要你帮他解决
他需要维护一个n点的无向图,目前有2个操作:
 1.加入一条连接a和b的无向边
 2.查询a和b的连通性
由于查询次数太多了,导致阿力觉得好烦,于是他决定用0或1代表每个询问的答案,将每个询问的答案依次从左到右排列,把得到的串视为一个二进制数,输出这个二进制数对998244353取模的值

Input

第一行 两个数 点个数n<=4000000,操作数目m<=8000000;
 接下来m行包括三个整数 k,a,b;
 k=0 执行1操作
 k=1 执行2操作

Output

一个数表示答案

Samples

input:
3 6 1 1 0 0 0 1 1 0 1 1 1 2 0 2 1 1 2 1
output:
5

Hint

答案串为101