Hide

Problem H
Mancala

Mancala is a family of board games played around the world, sometimes called sowing games, or count-and-capture games, which describes the game play. One simple variant is a solitaire game called Tchoukaillon which was described by Véronique Gautheron. Tchoukaillon is played on a board with an arbitrary number of bins numbered $1, 2, \ldots $, containing $b[1], b[2], \ldots $ counters respectively and an extra empty bin called the Roumba on the left.

\includegraphics[]{e1.png}

A single play consists on choosing a bin, $n$, for which $b[n] = n$ (indicated by the darker circles in the diagram) and distributing the counters one per bin to the bins to the left including the Roumba (getting the next diagram below in the figure above). If there is no bin where $b[n] = n$, then the board is a losing board.

If there is a sequence of plays which takes the initial board distribution to one in which every counter is in the Roumba, the initial distribution is called a winnable board. In the example above, $0,1,3,\ldots $ is a winnable board (the “$\ldots $” indicates all the bins to the right of bin $3$ contain $0$). For each total number of counters, there is a unique distribution of the counters to bins to make a winnable board for that total count (so $0,1,3,\ldots $ is the only winnable board with $4$ counters).

Write a program which finds the winnable board for a total count input.

Input

The first line of input contains a single integer $P$, ($1 \le P \le 200$), which is the number of data sets that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input. It contains the data set number, $K$, followed by a single space, followed by the total count $N$ ($1 \le N \le 2000$) of the winnable board to be found.

Output

For each data set there will be multiple lines of output. The first line of output contains the data set number, $K$, followed by a single space, followed by the index of the last bin, $B$, with a non-zero count. Input will be chosen so that $B$ will be no more than $80$. The first line of output for each dataset is followed by the bin counts $b[1], b[2], \ldots , b[B]$, 10 per line separated by single spaces.

Sample Input 1 Sample Output 1
3
1 4
2 57
3 500
1 3
0 1 3
2 12
1 2 2 2 2 6 2 4 6 8
10 12
3 39
0 2 2 1 3 2 2 2 6 7
5 0 6 12 2 6 10 14 18 1
3 5 7 9 11 13 15 17 19 21
23 25 27 29 31 33 35 37 39

Please log in to submit a solution to this problem

Log in