题目描述

使用ST表来预处理数组，快速查询任意区间的最大公约数（GCD）

输入格式

首先一行输入一个数字n，接着第二行输入n个数组元素，第三行输入需要查询的区间数q，接下来的q行输入q个区间。

输出格式

输出q个区间内所有元素的最大公约数

样例

输入样例 1

6
2 4 5 7 11 13
2
1 2
3 4

输出样例 1

区间[1,2]的GCD为: 2
区间[3,4]的GCD为: 1

输入样例 2

1
5
1
1 1

输出样例 2

区间[1,1]的GCD为: 5

输入样例 3

5
0 0 0 0 0
3
1 5
2 3
5 5

输出样例 3

区间[1,5]的GCD为: 0
区间[2,3]的GCD为: 0
区间[5,5]的GCD为: 0