背景

“树”

2022 年，我们在树上传输数据、建造军营。

2023 年，我们一起种树、装饰圣诞树。

2024 年，我们探寻树的新遍历方式、计算合法的新树个数。

2025 年，树的价值一题，创飞了无数考生。

而 2026 年，树会以什么样的方式出现在考场里呢？

题目描述

给定一棵树，根为 $1$，每个点有权值 $a_i$。

有 $q$ 次操作，每次操作是以下两种类型之一。

• 1 x y，将 $x$ 子树内所有点的权值与 $y$ 取最大公因数。

• 2 x，给定 $x$，求出 $x$ 子树内所有点权值的最小公倍数。

最小公倍数会很大，所以请输出答案对 $998244353$ 取模的结果。

输入格式

第一行两个正整数 $n,q$，表示树的节点数和操作数。

接下来一行 $n$ 个正整数，依次表示每个节点的初始权值。

接下来 $n-1$ 行每行两个正整数 $x,y$，表示树上 $x,y$ 之间有一条边。

接下来 $q$ 行每行形如 1 x y 或 2 x，代表一次操作。

输出格式

对于每次 $2$ 操作，输出一行一个正整数，表示最小公倍数对 $998244353$ 取模的结果。

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

420
84
2
30
3

5 8
997 991 997 2 997
1 2
2 3
3 4
4 5
2 1
1 3 1
2 1
2 3
1 1 2
2 1
1 5 1
2 1

1976054
988027
1
1
1

提示

本题采用捆绑测试。

对于 $100\%$ 的数据，满足 $1\le n,q,a_i,y\le10^5,1\le x\le n$。

特殊性质 A：根度数为 $n-1$。

特殊性质 B：树是一条链。

特殊性质 C：没有 $1$ 操作。