인스턴트 라면

우는 격렬한 훈련을 마친 뒤 배가 고파서 근처 가게에 좋아하는 인스턴트 라면을 사러 갔다. 우가 계산을 마치자 계산원이 흥미로운 문제를 냈다.

오른쪽 절반의 모든 정점에 양의 정수가 적혀 있는 이분 그래프가 주어진다. 왼쪽 절반 정점들의 부분집합 $S$에 대해, $N(S)$는 $S$의 정점 중 하나 이상과 인접한 오른쪽 절반 정점들의 집합이고, $f(S)$는 $N(S)$에 속한 정점에 적힌 수의 합이다. 공집합이 아닌 모든 부분집합 $S$에 대한 $f(S)$의 최대공약수를 구하라.

우는 훈련으로 지쳐서 이 문제를 풀 수 없다. 그를 도와주자!

첫 줄에 테스트 케이스의 개수 $t$ ($1 \leq t \leq 500\,000$)가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

각 테스트 케이스의 첫 줄에는 그래프 양쪽 절반의 정점 수 $n$과 간선 수 $m$ ($1 \leq n, m \leq 500\,000$)이 주어진다.

둘째 줄에는 오른쪽 절반 정점에 적힌 정수 $c_i$ ($1 \leq c_i \leq 10^{12}$) $n$개가 주어진다. $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을 넘지 않는다.

각 테스트 케이스마다 구한 최대공약수를 한 줄에 하나씩 출력한다.

정수 집합의 최대공약수는 집합의 모든 원소를 나누는 가장 큰 정수 $g$다.

첫 번째 테스트 케이스에서는 왼쪽 정점과 오른쪽 정점이 모두 서로 연결되어 있다. 따라서 공집합이 아닌 모든 부분집합 $S$에 대해 $f(S)$는 2이고, 이 값들의 최대공약수도 2다.

두 번째 테스트 케이스에서 왼쪽 집합 $\{1\}$은 오른쪽 정점 $\{1, 2\}$와 연결되어 있고, 그 합은 2다. 왼쪽 집합 $\{1, 2\}$는 오른쪽 정점 $\{1, 2, 3\}$과 연결되어 있고, 합은 3이다. 따라서 $f(\{1\}) = 2$, $f(\{1, 2\}) = 3$이며, 모든 $f(S)$ 값의 최대공약수는 1이다.