题目背景

xry终于发现了自己多年来一直这么弱的原因,一种叫蒻的物质始终包围这他。现在,xry要对它进行进一步的研究。

题目描述

xry找来了一棵无根树,在每一个点上有一个储存蒻的容器,初始所有容器中蒻的质量全部为1。

在xry的实验中,有时因为xry的特殊操作会使树上某一段路径上的容器中的蒻的质量呈整数倍增长。我们将一次增长事件描述为\(1\ x\ y\ v\),表示\(x\)到\(y\)的路径上所有的容器中蒻的质量变为了原来的\(v\)倍。

现在,xry发现由于一些未知原因,所有容器中的每一单位的蒻都是互不相同的,他决定设计一些合并容器并进行实验的方案。

对于一个方案,我们要合并树上一条路径中所有容器里的蒻。具体的合并方法是,从每一个容器中取出1个单位的蒻加到一起进行实验,由于每一单位的蒻互不相同,那么对于一个方案,就会有许多不同的实验可以进行。

显然不同的方案有不同的研究价值,于是我们定义一个方案的研究价值如下:

对于一个可以进行\(x\)个不同实验的方案,其研究价值\(V(x)=\sigma(x)\ mod\ 998244353\),其中\(\sigma(x)\)表示\(x\)所有正因子的和。

于是xry现在给出了一些合并容器的方案,我们将一个提出方案的事件描述为\(2\ x\ y\),表示xry提出一个将\(x\)到\(y\)的路径上所有容器进行合并的方案,现在他希望你告诉他提出某一方案时,这个方案的研究价值。

注意,一个合并方案只是一些尚待实行的方案,并不会真正改变容器中蒻的质量。

输入输出格式

由于数据强度未知(?),使用subtask进行测试。

输入格式

第1行一个整数\(type\),表示这组数据位于第几个subtask。

第2行2个整数\(n,q\),表示树上点的数量和事件数量。

第3行至第\(n+1\)行,每行两个整数\(u\ v\),表示树上两点\(u\)和\(v\)直接连边。

第\(n+2\)行至第\(n+q+1\)行,每行为\(1\ x\ y\ v\)表示一次增长,或为\(2\ x\ y\)表示提出一个合并方案。

输出格式

对于每一个被提出的合并方案输出一行一个整数,表示这个方案的研究价值。

输入输出样例

输入样例(当然\(type\)是假的)

233
5 6
1 3
3 5
2 3
4 1
1 5 2 2
2 2 1
1 5 4 3
1 1 1 5
2 5 4
2 3 4

输出样例

7
5082
720

样例解释

一开始的树长成这样(红色数字代表这个点上的容器中蒻的质量)

第一次增长使5到2的路径上所有容器中蒻的质量乘了2

询问一个合并2到1路径上所有容器的方案的研究价值,该方案可进行的不同实验数量为\(2\times2\times1\times1=4,V(4)=\sigma(4)=1+2+4=7\);

第二次增长使5到4的路径上所有容器中蒻的质量乘了3

第三次增长使1到1的路径上(即点1)所有容器中蒻的质量乘了5

询问一个合并5到4路径上所有容器的方案的研究价值,该方案可进行的不同实验数量为\(6\times6\times15\times3=1620,V(1620)=\sigma(1620)=5082\);

询问一个合并3到4路径上所有容器的方案的研究价值,该方案可进行的不同实验数量为\(6\times15\times3=270,V(270)=\sigma(270)=720\)。

数据范围

对于所有数据,满足\(1\le n,1\le q\),操作1,2满足\(1\le x,y\le n\),操作1满足\(1\le v\le 100\)。