D. Beautiful triplets
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$. A triple of numbers $$$(x, y, z)$$$ is called beautiful if the following conditions hold: $$$x$$$ is divisible by $$$y$$$ without a remainder, $$$y$$$ is divisible by $$$z$$$ without a remainder, and $$$x \gt y \gt z$$$.

You are given $$$q$$$ queries of the form $$$(l, r)$$$. For each query, you need to find indices $$$i \lt j \lt k$$$ in the array $$$a$$$ such that the triple $$$(a_i, a_j, a_k)$$$ is beautiful and $$$l \leq i \lt j \lt k \leq r$$$. Among all such triples, choose the one that maximizes the value $$$n^2 \cdot a_i + n \cdot a_j + a_k$$$. If there are multiple triples with the maximum value, choose the lexicographically smallest triple $$$(i, j, k)$$$.

Input

The first line contains a single integer $$$n$$$ — the length of the array $$$a$$$ ($$$1 \leq n \leq 10^{5}$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the elements of the array $$$a$$$.

The third line contains a single integer $$$q$$$ ($$$1 \leq q \leq 10^{5}$$$) — the number of queries.

Then follow $$$q$$$ lines, each of which contains two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) — the boundaries of the current query.

Output

For each query, output the triplet $$$(i, j, k)$$$ that is the answer to the query, if such a triple is found. If the triplet $$$(i, j, k)$$$ was not found, output $$$-1$$$.

Example
Input
8
8 4 2 1 4 2 8 1
4
2 4
2 7
1 7
3 5
Output
2 3 4
2 3 4
1 2 3
-1