GCD and K-th Query

Time limit1sMemory limit1024 MB

Summary

Given a sequence of N positive integers, answer queries for the K-th smallest gcd over all subarrays inside a range [L, R].

Problem

A sequence of positive integers $A_1, A_2, \dots, A_N$ of length $N$ is given. Write a program that processes the following queries.

$L$ $R$ $K$ : For every ordered pair $(i, j)$ with $L \leq i \leq j \leq R$ , compute $\gcd(A_i, A_{i+1}, \dots, A_j)$ . Sort these values in non-decreasing order and output the $K$ -th value.

Here $\gcd(A_i) = A_i$ .

For the sequence $(1, 2, 4)$ with $L = 1$ and $R = 3$ , the possible gcd values are $(1, 1, 1, 2, 2, 4)$ . If $K=4$ , the answer is $2$ .

The first line contains the length $N$ of the sequence. ( $1 \leq N \leq 20000$ )

The second line contains $N$ integers $A_1, A_2, \dots, A_N$ separated by spaces. ( $1 \leq A_i \leq 500000$ )

The third line contains the number of queries $Q$ . ( $1 \leq Q \leq 100000$ )

From the fourth line, each of the next $Q$ lines contains one query $L$ , $R$ , $K$ . ( $1 \leq L \leq R \leq N$ , $1 \leq K \leq (R-L+1)(R-L+2)/2$ )

For each query, print the result on its own line.

Example 1

Input

8
1 2 4 8 72 27 9 3
10
1 1 1
2 2 1
1 2 3
2 7 3
2 7 10
2 7 15
2 7 21
1 8 1
1 8 18
1 8 36

Expected output