众所周知，朱大师是宇宙中最强大的人。他拥有无限的力量来保护世界。

在朱大师的花园里长着一棵神奇的有根树。这棵树包含 $n$ 个顶点和 $n-1$ 条边。树的根节点是顶点 $1$。每个顶点 $i$ 包含的朱大师力量值为 $a_i$。

小六花是一个好奇的女孩：她有 $m$ 个问题要问朱大师。但现在朱大师正忙于保护我们的世界，所以他希望你帮他回答六花的问题。

每个六花的问题格式为 “$t\ u\ v\ a\ b$”。

• 如果 $t$ 为 $1$，则 $u$ 等于 $v$，六花关注以顶点 $u$ 为根的子树，并想知道 $S_a$ 和 $S_b$ 的 GCD（最大公约数），其中 $S_a$ 是该子树中出现次数恰好为 $a$ 次的数字之和，$S_b$ 是该子树中出现次数恰好为 $b$ 次的数字之和。
• 如果 $t$ 为 $2$，六花关注顶点 $u$ 和 $v$ 之间的简单路径，并想知道 $T_a$ 和 $T_b$ 的 GCD，其中 $T_a$ 是该路径上出现次数恰好为 $a$ 次的数字之和，$T_b$ 是该路径上出现次数恰好为 $b$ 次的数字之和。

这里，对于任何 $x$，我们定义 $\text{GCD}(x, 0) = \text{GCD}(0, x) = x$。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量 ($1 \le T \le 10$)。

每个测试用例的第一行包含两个整数 $n$ 和 $m$：神奇树的顶点数和六花的问题数 ($1 \le n, m \le 10^5$)。

下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$：每个顶点的朱大师力量值 ($1 \le a_i \le 10^9$)。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示连接顶点 $u$ 和 $v$ 的一条边 ($1 \le u, v \le n$)。保证这些边构成一棵树。

接下来的 $m$ 行，每行包含一个上述格式的六花问题 ($1 \le u, v \le n, 1 \le a, b \le n$)。

输出格式

对于每个六花的问题，在单独的一行中输出答案。

样例

输入 1

1
5 5
1 2 4 1 2
1 2
2 3
3 4
4 5
1 1 1 1 1
1 1 1 1 2
2 1 5 1 1
2 1 5 1 2
2 1 1 2 2

输出 1

4
1
4
1
0