B. Even Modulo Pair
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a strictly increasing sequence of positive integers $$$a_1 \lt a_2 \lt \ldots \lt a_n$$$. Find two distinct elements $$$x$$$ and $$$y$$$ from the sequence such that $$$x \lt y$$$ and $$$y \bmod x$$$ is even, or determine that no such pair exists.

$$$p \bmod q$$$ denotes the remainder from dividing $$$p$$$ by $$$q$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2\cdot 10^4$$$). The description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the length of the sequence.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_1 \lt \ldots \lt a_n\le 10^9$$$) — the given sequence.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case:

  • If no such pair exists, output -1.
  • Otherwise, output two integers $$$x$$$ and $$$y$$$ — the elements that satisfy the condition.

If there are multiple valid pairs, you may output any of them.

Example
Input
4
5
1 3 4 5 6
6
2 3 5 7 11 13
4
2 3 13 37
3
17 117 1117
Output
3 5
3 11
-1
17 1117
Note

Visualizer link

In the first test case, choosing $$$x = 3$$$ and $$$y = 5$$$ yields $$$y \bmod x = 5 \bmod 3 = 2$$$, which is even.

In the third test case, it is clear that no valid pair exists.