An ordering for the Cartesian product x of any two sets A and B with order relations <A and <B, respectively, such that if (a1, b1) and (a2, b2) both belong to AxB, then (a1, b1) < (a2, b2) iff either

• a1 <A a2, or
• a1 = a2 and b1 <B b2.

The lexicographic order can be readily extended to cartesian products of arbitrary length by recursively applying this definition, i.e., by observing that AxBxC = Ax(BxC).

When applied to subsets, two subsets are ordered by their smallest elements. For example, the subsets of {1,2,3} in lexicographic order are {}, {1}, {1,2}, {1,2,3}, {1,3}, {2}, {2,3}, {3}.

You will be given a subset of a set of first n natural numbers. You need to find k-th lexicographically next subset. Also we will consider that lexicographically last subset is followed by the first one in the ordering.

Input

The first line is number t - the amount of test cases. Each test case starts with numbers n and k. The next line describes the given subset. The description starts with number q - the amount of elements in the subset, followed by q natural numbers - the elements of the subset.

Constraints

1 <= t <= 5
1 <= n <= 50000
0 <= k <= 10000
0 <= q <= n

Output

For each test case output the k-th lexicographically next subset after the given one. If the result is an empty set then print "empty".

Example

Input:
3
3 1
1 3
3 3
2 1 3
5 5
0

Output:
empty
3
1 2 3 4 5