Problem - Range GCD Queries

Given an array, answer queries for $\gcd$ of elements in range $[l, r]$.

Example: arr $= [2, 6, 9, 3, 6]$

• Query $(0, 2)$: $\gcd(2, 6, 9) = 1$
• Query $(1, 4)$: $\gcd(6, 9, 3, 6) = 3$ $\gcd$ is idempotent: $\gcd(a, a) = a$.

So the overlap trick works. Just change the merge operation from $\min$ to $\gcd$. Constraints: up to $10^5$ elements, up to $10^5$ queries.