此题为交互式试题。
在一个遥远的国度中，人们使用着一套神秘的货币系统。在他们的货币系统中有 种不同的货币， 面值分别为 ，你可以假设每种货币的数量无限多。其中面值较小（即 ）的币种为硬币，记硬币的数量为 ；而面值较大（即 ）的币种为纸币，记纸币的数量为 。由于当地的特殊使用习惯，一些价格是可以通过组合这些货币表示出来的，而其他一些价格是不能被组合出来的。
现在你不知道这套货币系统的具体信息，包括 与 的具体数值。但你可以通过向当地人询问一个价格 能否由这些货币组合出来。当然，你需要询问尽量少的次数确定 与 。
因为不同的 与 可能可以达到相同的效果，所以你只需求出一种满足询问结果的答案。也就是说，对于所询范围内任意的 ，你的答案能否组合出 的结果应该与交互库的结果完全相同。
你需要实现一个函数 solve，解出这套货币系统的 与 的具体数值。
solve(type)
type 为该测试点的数据类型，具体见「数据规模和约定」。在每个测试点中，交互库都会调用恰好一次 solve 函数。在该函数中你需要调用函数query获取信息，调用函数answer提交答案。
你可以调用函数 query 来询问一个价格能否由货币组合出来，但是这个函数的调用次数不能超过 次。
query(v)
v 为你询问的价格，需要保证 ；你需要调用函数 answer 来提交答案，这个函数必须恰好调用 次。
answer(n, a)
n 为你求出的答案的元素个数，需要保证 ；a 表示一个大小为 数组，其中数组的第 个位置的数值为 ，数组从 下标开始，需要保证 。你需要且只能提交一个源文件 currency.cpp 实现上述函数，且遵循下面的命名和接口。
源代码中需要包含头文件 currency.h。
你需要实现的函数 solve：
void solve(int type);
函数 query 的接口信息如下：
bool query(long long v);
函数 answer 的接口信息如下：
void answer(int n, int *a);
你可以将附加文件中的 currency.cpp 作为模板开始编写程序。
C/C++ 以外的语言可以通过标准输入输出进行交互。
程序开始时，从标准输入读入一行，包含正整数 <type>，表示该组测试数据的类型。
此后，需要调用 query() 时，向标准输出输出一行 Q <v> 并刷新输出缓冲（例如 Pascal 语言的 flush(output) 和 Java 语言的 System.out.flush()，其他语言请参阅语言文档）；此后从标准输入读入一行，包含一个整数 或 表示询问结果。
需要调用 answer() 时，向标准输出输出两行：第一行形如 A <n>，第二行包含 个空格分隔的正整数 。
所有输出同样需要满足上述限制。
对于 的测试数据， ，交互库中的数据保证满足 的限制，但你提交的答案可以不满足该限制。
| 子任务 | 分值 | 的规模 | 的规模 | ||
|---|---|---|---|---|---|
| 1 | 6 | 1 | 1000 | ||
| 2 | 22 | 2 | 40 | ||
| 3 | 16 | 3 | 600 | ||
| 4 | 12 | 4 | 1000 | ||
| 5 | 28 | 5 | 2200 | ||
| 6 | 16 | 6 | 22000 |
g++ grader.cpp currency.cpp -o currency -O2
可执行文件将从标准输入读入数据，将结果输出到标准输出。
读入完成之后，交互库将调用 solve 函数。如果你调用 query 的次数超过 次，或调用 answer 的次数小于或大于 次，则交互库会输出错误信息，并退出。如果传入 query 函数和 answer 函数的参数非法，那么交互库会输出详细的错误信息，并退出。
当正确调用answer函数，solve 函数返回后，交互库会判断你提交的答案是否符合要求。如果答案正确，则会输出 Correct!，否则会输出 Incorrect!。
在编译命令中加入-DDEBUG可以使交互库输出更多调试信息。
如果要使用自己的输入文件进行测试，请保证输入文件符合格式以下要求，否则不保证程序能正确运行。
第一行包含两个整数 ，需要保证 。
第二行包含一个整数 ，需要保证 。
第三行包含 个整数，其中第 个数为 ，需要保证 且 与 满足 类型的限制。
请注意最终测评使用的 currency.h 与下发的文件并不一致。