You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 C 得到了一棵青蛙平衡树。这棵树上有 $n$ 只青蛙，有一些青蛙之间可以看作有边相连并且构成了一棵树，$1$ 号为根

我们定义两只青蛙的距离 $d_{i,j}$ 为两只青蛙最短路径上青蛙的数量（包括两端），一只青蛙 $i$ 的深度 $deep_i=d_{1,i}$。同时为了方便计算，我们定义青蛙 $j$ 对于它的祖先青蛙 $i$ 的相对深度 $Rdeep_{i,j}=deep_j-deep_i$

每只青蛙都有重量 $h_i$，因此平衡它们非常困难。青蛙 $j$ 对于它的祖先 $i$ 的平衡的影响值为 $v_{i,j}=h_j^{Rdeep_{i,j}}$

另外，它想知道对于 $i$ 的子树，从中任选 $k$ 只青蛙（假设为 $c_1,c_2,...,c_k$）的所有 $\prod\limits_j h_{c_j}$ 之和，记为 $r_{i,k}$

小 C 非常菜，所以经常需要你的帮助才能平衡，所以他会有以下操作：

1. 将第 $i$ 只青蛙的重量修改为 $v$
2. 查询对于第 $i$ 只青蛙的子树中的所有节点 $j$ 的 $v_{i,j}$ 之积
3. 查询对于第 $x$ 和第 $y$ 只青蛙的最短路径上的每个节点 $j$ 的 $v_{\text{LCA}(x,y),j}$ 之积
4. 查询第 $i$ 只青蛙的 $r_{i,k}$

由于这些数可能很大，答案对 $998244353$ 取模

输入格式

第一行两个数 $n,m$，表示青蛙数量和操作数量。

接下来一行 $n$ 个数 $h_i$。

接下来 $n-1$ 行每行两个数，表示一条边。

接下来 $m$ 行，每行格式为 1 i v 或 2 i 或 3 x y 或 4 i k。

输出格式

对于每一个 $2,3,4$ 操作，输出一行一个整数表示答案。

样例 #1

10 4
1 1 4 5 1 4 1 9 1 9
1 4
5 1
1 9
10 1
4 2
6 4
2 7
3 6
6 8
3 7 10
2 4
1 6 9
4 4 1

45
5184
29

提示

第一个查询：$1^3\times 1^2\times 5^1\times 1^0\times 9^1=45$

第二个查询：$5^0\times 1^1\times 4^1\times 1^2\times 4^2\times 9^2=5184$

第三个查询：$5+1+9+1+4+9=29$

$1\leq n,m\leq 10^5,1\leq h_i,v\leq 10^9,1\leq i,x,y\leq n,1\leq k\leq 10$

特殊性质 A：保证没有 $4$ 操作

特殊性质 B：保证输入的树是一条链。

特殊性质 C：保证输入的树是菊花图。