C. 评测机

玉米高中的Online Judge终于抛弃了陪伴自己十年的评测机，换上了一大批新的玉米评测机。

这些玉米的排列方式很奇怪，它们形成了一个树形结构。

每个玉米都有自己的性能。由于玉米是很简单的生物，所以它们的性能值也很简单：没有 、、、、 之外的质因子（也就是都可以表示为 的形式）。

当一些玉米启动时，总的性能值是每个玉米的性能值之积的约数和 的值。

现在要进行一些测试：每次选定树上一条链上的玉米启动，求总性能值。

从文件 onlinejudge.in 中读入数据。

第1行两个整数 和 ：玉米个数和测试次数。

第2行 个整数 ：每个玉米的性能。

第3行到第n+1行，每行两个整数 和 ，表示 和 之间有一条边。

第n+2行到第n+m+1行，每行两个整数 和 ，表示询问启动树上 到 的链上所有玉米的总性能值。

向文件 onlinejudge.out 中输出答案。

输出m行，第i行表示第 个询问的答案。

样例输入1

5 3
18 12 25 7 33
1 2
2 3
2 4
3 5
1 4
2 4
2 5

样例输出1

4800
224
33852

见附加文件中的 onlinejudge1.in/out

样例说明1

号到 号经过的玉米为 号、 号和 号，它们的性能分别为 、、，性能之积为

的约数有： 它们的和为 ，即： 的约数和为

号到 号经过的玉米为 号和 号，性能之积为 容易得出 的约数和为

号到 号经过的玉米为 、、 号，性能之积为 容易得出 的约数和为

样例输入输出2

见附加文件中的 onlinejudge2.in/out

此样例与测试点8规模、性质相同

样例输入输出3

见附加文件中的 onlinejudge3.in/out

此样例与测试点14规模、性质相同

所有测试点满足：

数据存在一定梯度，编号为奇数的测试点数据随机