World — Eolymp

Input

The first line contains an integer $n$ ( $3 \leq n \leq 4 \cdot 1 0^{5}$ 3 \le n \le 4 \cdot 10^5) — the length of the array $a$ .

The second line contains $n$ integers $a_{1}, a_{2}, ... a_{n}$ a_1,a_2,...a_n ( $1 \leq a_{i} \leq 2 \cdot 1 0^{5}$ 1 \le a_i \le 2 \cdot 10^5) — the elements of the array.

The third line contains an integer $q$ ( $1 \leq q \leq 1 0^{5}$ 1 \le q \le 10^5) – the number of queries.

The next $q$ lines contain two numbers $l$ , $r$ ( $1 \leq l < r \leq n$ 1 \le l < r \le n, $r - l + 1 \geq 3$ r-l+1 \ge 3) — the queries.

Output

For each query, output three numbers - the answer to the query, or $- 1$ if the corresponding triple does not exist. The indices may be output in any order. If there are several correct answers, any of them is allowed.

Examples

Example 1

Loading

Example 2

Loading

Note

Explanation for the first example

For the first query, $g cd (a_{1}, a_{2}) = 2 > 1$ \gcd(a_1,a_2) = 2 > 1, $g cd (a_{1}, a_{3}) = 3 > 1$ \gcd(a_1,a_3) = 3 > 1, $g cd (a_{2}, a_{3}) = 5 > 1$ \gcd(a_2,a_3) = 5 > 1, so the triple $(1, 2, 3)$ (1,2,3) satisfies the condition of the problem. Note that another possible answer is the triple $(1, 2, 4)$ (1,2,4).

For the second query, for the only triple $(2, 3, 4)$ (2,3,4), $g cd (a_{2}, a_{3}) = 1$ \gcd(a_2,a_3) = 1, so no answer exists.

Scoring

Subtask $1$ ( $10$ points): $n, q \leq 50$ n, q \le 50
Subtask $2$ ( $50$ points): $q = 1$ q = 1
Subtask $3$ ( $50$ points): $a_{i} = p^{k}$ a_i = p^k, where $p$ is some prime number
Subtask $4$ ( $50$ points): $n, q \leq 1000$ n, q \le 1000
Subtask $5$ ( $50$ points): for each query, if an answer exists, then there exists an answer with $i = l$ i = l and $k = r$ k = r
Subtask $6$ ( $190$ points): Without additional constraints