Instant Noodles

문제

Wu got hungry after an intense training session, and came to a nearby store to buy his favourite instant noodles. After Wu paid for his purchase, the cashier gave him an interesting task.

You are given a bipartite graph with positive integers in all vertices of the right half. For a subset $SS$ of vertices of the left half we define $N(S)N(S)$ as the set of all vertices of the right half adjacent to at least one vertex in $SS$, and $f(S)f(S)$ as the sum of all numbers in vertices of $N(S)N(S)$. Find the greatest common divisor of $f(S)f(S)$ for all possible non-empty subsets $SS$.

Wu is too tired after his training to solve this problem. Help him!

입력

The first line contains a single integer $tt$ ($1\le t\le 5000001\; \backslash leq\; t\; \backslash leq\; 500\backslash ,000$) --- the number of test cases in the given test set. Test case descriptions follow.

The first line of each case description contains two integers $nn$ and $mm$ ($1\le n,m\le 5000001\; \backslash leq\; n,\; m\; \backslash leq\; 500\backslash ,000$) --- the number of vertices in either half of the graph, and the number of edges respectively.

The second line contains $nn$ integers $c_{i}c\_i$ ($1\le c_i\le {10}^{12}1\; \backslash leq\; c\_i\; \backslash leq\; 10^\{12\}$). The $ii$-th number describes the integer in the vertex $ii$ of the right half of the graph.

Each of the following $mm$ lines contains a pair of integers $u_{i}u\_i$ and $v_{i}v\_i$ ($1\le u_i,v_i\le n1\; \backslash leq\; u\_i,\; v\_i\; \backslash leq\; n$), describing an edge between the vertex $u_{i}u\_i$ of the left half and the vertex $v_{i}v\_i$ of the right half. It is guaranteed that the graph does not contain multiple edges.

Test case descriptions are separated with empty lines. The total value of $nn$ across all test cases does not exceed $500000500\backslash ,000$, and the total value of $mm$ across all test cases does not exceed $500000500\backslash ,000$ as well.

출력

For each test case print a single integer --- the required greatest common divisor.

힌트

The greatest common divisor of a set of integers is the largest integer $gg$ such that all elements of the set are divisible by $gg$.

In the first sample case vertices of the left half and vertices of the right half are pairwise connected, and $f(S)f(S)$ for any non-empty subset is $22$, thus the greatest common divisor of these values if also equal to $22$.

In the second sample case the subset $\{1\}\backslash \{1\backslash \}$ in the left half is connected to vertices $\{1,2\}\backslash \{1,\; 2\backslash \}$ of the right half, with the sum of numbers equal to $22$, and the subset $\{1,2\}\backslash \{1,\; 2\backslash \}$ in the left half is connected to vertices $\{1,2,3\}\backslash \{1,\; 2,\; 3\backslash \}$ of the right half, with the sum of numbers equal to $33$. Thus, $f(\{1\})=2f(\backslash \{1\backslash \})\; =\; 2$, $f(\{1,2\})=3f(\backslash \{1,\; 2\backslash \})\; =\; 3$, which means that the greatest common divisor of all values of $f(S)f(S)$ is $11$.

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

2
1
12