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.

小仓鼠李华去的小学是一所发展飞快的学校。学校有 $n$ 个路口与 $n - 1$ 条连接两个路口的道路，且每两个路口之间都可以通过道路直接或间接到达。每个路口都建有一栋楼，第 $i$ 个路口的楼高为 $h_i$。李华经常会从其中一个路口走到另一个路口，在走的过程中，它会记录下所能看到的每栋楼的高度，且不会重复记录同一栋楼。

当李华走到路口 $v$ 时，它能看到 $v$ 以及所有与 $v$ 相邻路口（即通过一条路直接连接的路口）的楼。李华对校园很熟悉，所以不会绕路，也就是说，对于每一对路口 $(u, v)$，它从 $u$ 到 $v$ 的路线都是唯一的。每次李华结束行程后，它都想知道记下来的所有楼高度的均值和方差。

提示：$k$ 个数 $a_1, a_2, \dots, a_k$ 的均值和方差为：

另外，学校也在发展，包括以下两类事件：

1. 取一对点 $(u, v)$，将 $u$ 到 $v$ 的路径上（包含端点）所有的楼进行加盖操作，其高度均增加 $h$；
2. 取一对点 $(u, v)$，将 $u$ 到 $v$ 的路径上（包含端点）所有高度超过 $H$ 的楼进行降沉操作，通过挖地将低楼层降沉至地下，使楼高减小至 $H$。

现在给定学校发展和李华行程发生的顺序，请你求出每次行程记录的楼的均值和方差。李华非常讨厌小数，所以请将答案对 998244353 取模。具体来说，若答案可以表示为 $\frac pq$，请输出 $p \cdot q^{-1}$ 对 998244353 取模的值，其中 $q^{-1} \cdot q \equiv 1 (\bmod 998244353)$。

Input

输入第一行：两个整数 $n, m$（$1 \le n \le 10^5, 1 \le m \le 10^5$），表示学校的路口个数，以及发生的事件数量。

第二行：$n$ 个整数 $h_1, h_2, \dots, h_n$（$1 \le h_i \le 10^8$），表示初始时每栋楼的高度。

接下来 $n - 1$ 行：每行两个整数 $u, v$（$1 \le u, v \le n$），表示每条道路。

接下来 $m$ 行：每行描述一个事件（$1 \le u, v \le n$），格式如下：

• 1 $u$ $v$ $h$：第 $1$ 类学校发展事件，$1 \le h \le 5000$；
• 2 $u$ $v$ $H$：第 $2$ 类学校发展事件，$1 \le H \le 5 \times 10^8$；
• 3 $u$ $v$：李华行程事件，从 $u$ 走到 $v$。

Output

输出若干行：对于每次行程，输出李华希望得到的均值和方差，对 998244353 取模。

Examples

Sample Input 1

7 5
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
3 7
3 1 7
1 3 6 5
3 4 7
2 4 5 1
3 1 4

Sample Output 1

399297745 878455036
570425350 40744678
199648873 718735942

样例中，学校地图如下：

初始时各楼高度分别为 1 2 3 4 5 6 7，李华从路口 1 走到路口 7，经过的路口为 1 3 7，看到的楼的编号为 1 2 3 6 7，高度分别为 1 2 3 6 7，均值为 $\frac{19}5$，方差为 $\frac{134}{25}$。

学校第一次发展，路口 3 到路口 6 的路径上所有的楼高增加 5，各楼高度变成 1 2 8 4 5 11 7，李华从路口 4 走到路口 7，经过的路口为 4 2 1 3 7，能看到所有的楼，均值为 $\frac{38}7$，方差为 $\frac{516}{49}$。

学校第二次发展，路口 4 到路口 5 的路径上所有高度超过 1 的楼进行降沉操作，各楼高度变成 1 1 8 1 1 11 7，李华从路口 1 走到路口 4，经过的路口为 1 2 4，看到的楼的编号为 1 2 3 4 5，高度分别为 1 1 8 1 1，均值为 $\frac{12}5$，方差为 $\frac{196}{25}$。