Second International Programming Contest
March 28, 2004, Blagoevgrad, Bulgaria

Problem A

Let n be a positive integer. A composition of n into k parts is called a representation of the form n = a1 + a2 +...+ ak, where 0 <= ai <= n,  i = 1, .., k, are integers. For example, for n = 6 and k = 3, possible different compositions are 6 = 6 + 0 + 0, 6 = 1 + 2 + 3, 6 = 0 + 0 + 6, and so on. For fixed n and k, we arrange all the compositions in an increasing lexicographic order (1 < n < 1000, 1 < k < 1000). We assume that the composition a1 + a2 +...+ ak is greater than another composition b1 + b2 +...+ bk   in the lexicographic order, if there exists an index p,  p = 1, 2, …, k, so that ap > bp, but aj = bj  for any j < p.

Write a program, which for a given composition finds the next one. It is assumed that the given composition is not the last one in the lexicographic ordering. 

Your program should read several input data sets, each containing a composition. On the first line of the input, the number of data sets is given. This number will not exceed 20. Each data set consists of two subsequent lines. The first of them contains number k. The second line contains a composition in which the numbers are separated by a single space. The result should be written into the standard output, one composition at a line for each input set. In the output compositions, the numbers should be separated by a single space.

Example

Input

3
3
5 0 1
6
1 21 0 0 7 8
3
1 0 1

Output

5 1 0
1 21 0 0 8 7
1 1 0