E. Magic Subsequence
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Starlight Glimmer has a magic sequence $$$v_1,v_2,v_3,\dots,v_n$$$ of length $$$n$$$, she wants to find two different subsquence of it, which has the same sum.

Formally, find out sets $$$S_1=\{p_1,p_2,\dots,p_{|S_1|}\}$$$ and $$$S_2=\{q_1,q_2,\dots,q_{|S_2|}\}$$$ such that:

  • $$$1\le p_i,q_i\le n$$$.
  • $$$S_1\not=S_2$$$.
  • $$$\sum_{i=1}^{|S_1|} v_{p_i} = \sum_{i=1}^{|S_2|} v_{q_i}$$$

Note that the elements of a set are not repeatable.

Input

There are multiple test cases. The first line contains an integer $$$T$$$ ($$$1\le T\le 5$$$) indicating the number of test cases, for each test case:

The first line contain an integers $$$n$$$ ($$$1\le n\le 10^5$$$) indicating the length of the sequence.

The second line contain $$$n$$$ integers $$$v_1, v_2, \ldots, v_n$$$ ($$$1\le v_i\le 2\times 10^7$$$), represents the magic sequence.

Output

For each test case, if no set can be found that satisfies the above requirements, print a single "-1" (without quotes) on a line. Otherwise print two lines, each line prints a set in the following way:

First prints the size $$$k$$$ of the set, then prints $$$k$$$ integers representing the contents of the set, separated by spaces.

Example
Input
3
4
6 9 8 7
5
6 13 11 9 12
7
24 23 106 20 11 17 22
Output
2 4 3 
2 2 1 
-1
5 2 1 7 6 4 
1 3