E. Perfect Couple
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Consider the function

$$$$$$ f(x, y) = x^3 y - x y^3 $$$$$$

For a positive integer $$$m$$$, two integers $$$x$$$ and $$$y$$$ are called an $$$m$$$-perfect couple if $$$f(x, y)$$$ is divisible by $$$m$$$.

You are given an array of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ and $$$q$$$ queries. Each query consists of three integers $$$l$$$, $$$r$$$ and $$$m$$$.

For each query, find an $$$m$$$-perfect couple in the subarray $$$a_l, a_{l+1}, \dots, a_r$$$, or report that there is none. Formally, find two distinct indices $$$i$$$ and $$$j$$$ such that $$$l \le i, j \le r$$$ and $$$a_i$$$ and $$$a_j$$$ are an $$$m$$$-perfect couple, or report that no such pair of indices exists.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 10^6$$$, $$$1 \le q \le 10^5$$$) — the size of the array and the number of queries.

The second line of each test case contains $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array.

Each of the next $$$q$$$ lines contains three space-separated integers $$$l$$$, $$$r$$$ and $$$m$$$ ($$$1 \le l \lt r \le n$$$, $$$2 \le m \le 100$$$) — the description of a query.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$ and the sum of $$$q$$$ over all test cases doesn't exceed $$$10^5$$$.

Output

For each query, output the answer in a line.

If an $$$m$$$-perfect couple exists in the subarray $$$a_l, a_{l+1}, \dots, a_r$$$, output two space-separated integers $$$i$$$ and $$$j$$$ ($$$l \le i, j \le r$$$, $$$i \ne j$$$) such that $$$a_i$$$ and $$$a_j$$$ are an $$$m$$$-perfect couple. If there are multiple answers, you may output any of them.

Otherwise, output $$$-1$$$.

Example
Input
2
5 4
16 15 11 9 4
1 3 7
1 4 7
1 3 5
4 5 10
2 2
15 10
1 2 4
1 2 6
Output
-1
1 4
1 2
4 5
-1
1 2
Note

In the first query of the first test case, $$$f(16, 15) = 7440$$$, $$$f(16, 11) = 23760$$$ and $$$f(15, 11) = 17160$$$. None of them is divisible by $$$7$$$.

In the second query of the first test case, $$$f(16, 9) = 25200 = 7 \times 3600$$$. So, $$$a_1$$$ and $$$a_4$$$ are a $$$7$$$-perfect couple.

In the third query of the first test case, $$$f(16, 15) = 7440$$$, $$$f(16, 11) = 23760$$$ and $$$f(15, 11) = 17160$$$ are all divisible by $$$5$$$. So, the pairs of indices $$$(1, 2)$$$, $$$(1, 3)$$$ and $$$(2, 3)$$$ are all correct answers.

In the fourth query of the first test case, $$$f(9, 4) = 2340$$$, which is divisible by $$$10$$$.

In the second test case, $$$f(15, 10) = 18750$$$, which is divisible by $$$6$$$, but not by $$$4$$$.