PARTIT  Partition
A partition of positive integer m into n components is any sequence a_{1},...,a_{n} of positive integers such that a_{1}+...+a_{n}=m and a_{1}<=a_{2}<=...<=a_{n}. Your task is to determine the partition, which occupies the kth position in the lexicographic order of all partitions of m into n components.
The lexicographic order is defined as follows: sequence a_{1},...,a_{n} comes before b_{1},...,b_{n} iff there exists such an integer i,1<=i<=n, that a_{j}=b_{j} for all j, 1<= j< i, and a_{i}< b_{i}.
Input
The input begins with the integer t, the number of test cases. Then t test cases follow.
For each test case the input consists of three lines, containing the positive integers m, n and k respectively (1<=n<= 10, 1<= m<=220, k is not larger than the number of partitions of m into n components).
Output
For each test case output the ordered elements of the sought partition, separated by spaces.
Example
Sample input: 1 9 4 3 Sample output: 1 1 3 4
hide comments
minhthai:
20160321 15:48:19
didn't think it is DP at first sight. Thanks for the nice problem!


kejriwal:
20150918 00:15:28
nice dp :D 

paras meena:
20141231 17:41:04
silly mistake got 4+ WA :( 

nikhil:
20140117 11:50:22
more test cases plz...

Added by:  adrian 
Date:  20040719 
Time limit:  7s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  VI Polish Collegiate Team Programming Contest (AMPPZ), 2001 