BCS Mid Wales Programming Contest 2021

You are building a patio, which is made up of stone paving slabs and grout (the material between the slabs which holds the patio together).

You need to lay a row of paving slabs to start the construction of a patio. You have bought a set of slabs of various different lengths. Which slabs should you choose from the set in order to fill the row perfectly? Remember that you'll need to leave a 1 cm gap for grout between each slab, and also a 1 cm gap for grout at either end of the row.

Input

The first line of input gives you the number of test cases. For each subsequent test case, there are three lines of input. In the first line you are given a positive integer representing the total length in cm of the row that you need to fill. The next line gives you a positive integer stating the number of patio slabs available. The third line gives the lengths in cm of the patio slabs that you have available, separated by spaces.

Output

Output the set of slab lengths that you have chosen, sorted in descending order, and separated by spaces. If there is no solution, output -1. If there are multiple solutions, output the solution that makes use of the largest of the slabs.

Example

Input:
2
100
9
20 40 30 24 31 18 55 40 23
50
4
20 20 30 40

Output:
55 23 18
-1