C. Лапша быстрого приготовления
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ву проголодался после интенсивной тренировки и отправился в ближайший магазин, чтобы приобрести его любимую лапшу быстрого приготовления. После того, как Ву расплатился, кассир задал ему интересную задачу.

Дан двудольный граф, в вершинах правой доли которого записаны положительные целые числа. Для подмножества вершин $$$S$$$ левой доли определим $$$N(S)$$$ как множество вершин правой доли, смежной хотя бы с одной из вершин $$$S$$$, а $$$f(S)$$$ — как сумму чисел, записанных в вершинах $$$N(S)$$$. Требуется найти наибольший общий делитель чисел $$$f(S)$$$ для всех возможных непустых подмножеств $$$S$$$ (полагайте, что НОД пустого множества равен $$$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$$$.

Выходные данные

Для каждого тестового случая выведите единственное число — искомый наибольший общий делитель.

Пример
Входные данные
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
Примечание

Наибольшим общим делителем множества чисел называется наибольшее целое число $$$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$$$.