#920. [Lydsy1708月赛]记忆中的背包

[Lydsy1708月赛]记忆中的背包

Description

经过一天辛苦的工作,小Q进入了梦乡。他脑海中浮现出了刚进大学时学01背包的情景,那时还是大一萌新的小Q解

决了一道简单的01背包问题。这个问题是这样的:给定n个物品,每个物品的体积分别为v_1,v_2,...,v_n,请计算

从中选择一些物品(也可以不选),使得总体积恰好为w的方案数。因为答案可能非常大,你只需要输出答案对P取

模的结果。因为长期熬夜刷题,他只看到样例输入中的w和P,以及样例输出是k,看不清到底有几个物品,也看不

清每个物品的体积是多少。直到梦醒,小Q也没有看清n和v,请写一个程序,帮助小Q一起回忆曾经的样例输入。

Format

Input

第一行包含一个正整数T(1<=T<=100),表示测试数据的组数。

接下来T行,每行3个整数w,P,k(50<=w<=20000,1<=P<=2^30,0<=k<=min(20000,P-1))

分别表示每组需要回忆的测试数据的相关参数。

Output

对于每组数据,第一行输出n(1<=n<=40)。

第二行输出n个正整数v_1,v_2,...,v_n(1<=v_i<=20000),分别表示每个物品的体积。

若有多组可行解,输出任意一组。输入数据保证对于每组数据至少存在一组可行解。

Samples

4
50 1013 4
50 3 1
80 5 1
100 1000000007 13
5
10 20 20 30 50
5
10 20 20 30 50
8
10 20 30 40 50 60 70 80
11
12 18 20 13 41 30 15 11 11 250 28