GCD와 K번째 쿼리

시간 제한1초메모리 제한1024 MB

요약

길이 N의 양의 정수 수열에서 구간 [L, R] 안의 모든 부분 배열 gcd 값을 정렬했을 때 K번째 값을 구합니다.

문제

길이가 $N$ 인 양의 정수 수열 $A_1, A_2, \dots, A_N$ 이 주어진다. 다음 쿼리를 처리하는 프로그램을 작성하시오.

$L$ $R$ $K$ : $L \leq i \leq j \leq R$ 을 만족하는 모든 순서쌍 $(i, j)$ 에 대해 $\gcd(A_i, A_{i+1}, \dots, A_j)$ 를 구한다. 이 값들을 비내림차순으로 정렬했을 때 $K$ 번째로 나오는 수를 출력한다.

단, $\gcd(A_i) = A_i$ 로 정의한다.

길이가 $3$ 인 수열 $(1, 2, 4)$ 에서 $L = 1$ , $R = 3$ 일 때 나올 수 있는 $\gcd$ 값은 $(1, 1, 1, 2, 2, 4)$ 이다. 이때 $K=4$ 라면 $2$ 를 출력한다.

첫째 줄에 수열의 길이 $N$ 이 주어진다. ( $1 \leq N \leq 20000$ )

둘째 줄에 $N$ 개의 정수 $A_1, A_2, \dots, A_N$ 이 공백으로 구분되어 주어진다. ( $1 \leq A_i \leq 500000$ )

셋째 줄에 쿼리의 개수 $Q$ 가 주어진다. ( $1 \leq Q \leq 100000$ )

넷째 줄부터 $Q$ 개의 줄에 걸쳐 쿼리 $L$ , $R$ , $K$ 가 한 줄에 하나씩 주어진다. ( $1 \leq L \leq R \leq N$ , $1 \leq K \leq (R-L+1)(R-L+2)/2$ )

쿼리의 결과를 한 줄에 하나씩 출력한다.

예제 1

입력

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

예상 출력