Static Range GCD Query

Given a static array nums, answer multiple range queries asking for the greatest common divisor of all values in a subarray. Since gcd is associative and the array does not change, a sparse table can answer each query efficiently after preprocessing.

Input Format

nums = static integer array, queries = range gcd requests

Output Format

gcd value for each query, in order

Constraints

• 1 <= nums.length <= 10^5
• 1 <= queries.length <= 10^5
• Each query is [left, right] with 0 <= left <= right < nums.length.

Examples

nums = [24,36,48,18]
queries = [[0,2],[1,3]]

[12,6]

nums = [10,15,25]
queries = [[0,1],[1,2]]

[5,5]