D GCD of an Array

题目描述

你有一个长度为的数组.你需要处理个操作，格式是：输入两个数和，将乘以.
每次操作之后，你需要输出数组所有元素的GCD.
因为答案可能很大，所以模再输出

输入

第一行由两个整数组成：和
第二行由个整数组成 ——操作前的数组的元素
接下来q行是操作，每行输入两个整数和

输出

输出行，对于每个操作输出数组元素的GCD模以的值

样例

输入

4 3
1 6 8 12
1 12
2 3
3 3

输出

2
2
6

注意

第一次操作之后，数组是
第二次操作之后，数组是
第三次操作之后，数组是
这里表示做大公约数