吴老师在紧张的训练后肚子饿了,就来到附近的商店买了他最喜欢的方便面。吴付完钱后,收银员给了他一个有趣的任务。
给定一个二分图,右半部分的所有顶点均为正整数。对于左半部顶点的子集 $$$S$$$,我们将 $$$N(S)$$$ 定义为与 $$$S$$$ 中至少一个顶点相邻的右半部所有顶点的集合,并将 $$$f(S)$$$ 定义为 $$$N(S)$$$ 顶点中所有数字的总和。求所有可能的非空子集$$$S$$$的$$$f(S)$$$的最大公约数(假设空集的GCD为$$$0$$$)。
吴在训练后太累了,无法解决这个问题。帮助他!
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 500\,000$$$) - 给定测试集中的测试用例数量。测试用例描述如下。
每个案例描述的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1~\leq~n,~m~\leq~500\,000$$$) - 分别是图的两半中的顶点数和边数。
第二行包含 $$$n$$$ 整数 $$$c_i$$$ ($$$1 \leq c_i \leq 10^{12}$$$)。第 $$$i$$$ 数字描述了图右半部分顶点 $$$i$$$ 中的整数。
以下 $$$m$$$ 行中的每一行都包含一对整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$),描述左半部分的顶点 $$$u_i$$$ 和右半部分的顶点 $$$v_i$$$ 之间的边。保证图不包含多条边。
测试用例描述用空行分隔。所有测试用例的 $$$n$$$ 总价值不超过 $$$500\,000$$$,所有测试用例的 $$$m$$$ 总价值也不超过 $$$500\,000$$$。
输出
对于每个测试用例,打印一个整数 - 所需的最大公约数。
示例
输入 #1
3 2 4 1 1 1 1 1 2 2 1 2 2 3 4 1 1 1 1 1 1 2 2 2 2 3 4 7 36 31 96 29 1 2 1 3 1 4 2 2 2 4 3 1 4 3
输出 #1
2 1 12
注意
一组整数的最大公约数是最大整数 $$$g$$$,使得该集合的所有元素都可以被 $$$g$$$ 整除。
在第一个示例中,左半部分的顶点和右半部分的顶点是成对连接的,任何非空子集的 $$$f(S)$$$ 是 $$$2$$$,因此这些值的最大公约数也等于 $$$2$$$。
在第二个示例中,左半部分的子集 $$$\{1\}$$$ 连接到右半部分的顶点 $$$\{1, 2\}$$$,数字之和等于 $$$2$$$,左半部分的子集 $$$\{1, 2\}$$$ 连接到顶点 $$$\{1, 2,右半部分的3\}$$$,数字之和等于$$$3$$$。因此,$$$f(\{1\}) = 2$$$,$$$f(\{1, 2\}) = 3$$$,这意味着$$$f(S)$$$的所有值的最大公约数是$$$1$$$。