One day, Farouk was playing with a set of equilateral triangles and rods of various lengths. In this game, he chooses three rods, and he wants to place them inside some triangle such that they all meet at a point, and each one touches a side of the triangle at a right angle. He found this very satisfying and so he decided to ask for your help.
You are given an array of distinct even integers $$$l_1, l_2, \cdots, l_n$$$ representing the side lengths of $$$n$$$ equilateral triangles. You will be given $$$q$$$ queries where each query consists of three integers $$$d_1,$$$ $$$d_2$$$, and $$$d_3$$$ representing the squared perpendicular distances to the sides of the triangle. For each query, output the index of any triangle which contains a valid point $$$P$$$ strictly inside the triangle such that the perpendicular distances from $$$P$$$ to the sides of the triangles satisfy the distances given in the query, or determine that no such triangle exists.
The first line contains two integers $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) and $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of triangles and the number of queries, respectively.
The second line contains $$$n$$$ distinct even integers $$$l_i$$$ ($$$1 \le l_i \le 10^6$$$) — the side lengths of the equilateral triangles.
Each of the following $$$q$$$ lines contains three integers $$$d_1,$$$ $$$d_2$$$, and $$$d_3$$$ ($$$0 \lt d_1, d_2, d_3 \le 10^{18}$$$) — the squared perpendicular distances to each side of a triangle.
For each query, output the index of any triangle which contains some point whose perpendicular distances matches those of the query. If there are multiple solutions, output any of them. If no triangle satisfies the query, output -1 instead.
3 3 14 6 12 3 3 3 48 3 12 24 6 6
2 1 -1
10 5 86 52 32 66 88 62 6 98 68 16 5716 2585 2439 363 48 3 4655 735 5309 5109 468 2471 6627 3 3
-1 3 -1 -1 8
In the first test, the following illustrations show valid points for the first and second queries.
 |  |
| Triangle with side length 6 satisfying the first query. | Triangle with side length 14 satisfying the second query. |
For the third query, it can be shown that none of the given triangles contain a point with the required distances.
