Joe the Jock is spending the day at the gym, and he needs a certain amounts of weight for his benchpress sets.

The gym has several different types of weights, each no more than 100kg. There are an unlimited number of each type of weight.

Spare Joe the math and write a program to figure out what weights he should lift.

He thinks the bigger weights look a lot more impressive, so make sure to give him the biggest weights possible (e.g. 3,2,2 would be better than 3,2,1,1).

Unfortunately, it might also be impossible to reach the desired weight in any way.

Input

The first line is T (<50), the number of sets Joe has to do. Each of the T set descriptions are followed by a line.

The first line of each set is the total weight Joe needs, in decigrams (tenths of a gram), not more than 10^6. The second line is N (<100), the number of distinct denominations of weight. The following N lines are the weights, in decigrams.

Output

Separate the solutions for the sets by a blank line.

For each set, output one line for each type of weight he will use at least once, from heaviest to lightest. Each line will have the weight (in decigrams), a single space, and the number of that type of weight.

If a set is impossible to make, output a single line -1 instead.

Example

Input:
3

10
3
3
1
2

5
1
10

4799
5
2
3
6
7
42

Output:
3 3
1 1

-1

42 114
7 1
2 2