题目描述

Mca 市的地铁公司决定采取一项新措施——勿需购票，投币上车。有传闻说此举是为了减少乘客购票的排队时间。地铁运营商找到了本市计算机协会（Association for Computing Machinery，ACM）旗下的自动收款机（Automated Checkout Machine，ACM）公司，要求开发一款自动兑换机（Automatic exChange Machine，ACM）来满足乘客的需求。他们雇用你来担任首席程序员为此机器编写程序。自动兑换机内部存放有各种面值的硬币，当乘客将纸币放入机器时，机器会自动根据当前可用的硬币面值将乘客的纸币兑换成等值的硬币。当然，乘客不愿意口袋里面装着一大堆硬币去挤地铁，因此兑换成的硬币数量越少越好。如果现有的硬币面值无法完成兑换要求，应该输出一行信息，提示乘客需要寻求人工窗口的服务。

输入格式

输入包含多组测试数据。

第一行一个整数 $T$，表示数据组数。每组测试数据一行，第一个为整数 $c$，表示硬币面值的种类，接下来是 $c$ 个整数，每个整数 $d_i（1 \leq i \leq c）$ 表示一种硬币的面值，以美分为单位，最后是一个实数 $m$，表示乘客需要兑换的纸币的总面值，以美元为单位。

输出格式

对于每行输入均输出一行，如果不存在兑换方案，输出 No solution.。否则，按以下格式输出具有最少硬币数量的兑换方案：首先输出方案中硬币的总个数，然后一个空格，接着按照样例输出的格式打印兑换序列，即依照面值从小到大的顺序，将方案使用的各个面值及其对应的硬币个数予以输出。如果存在多种具有最少硬币数量的兑换方案，输出字典序（即按 ASCII 序）最小的兑换方案。

6
6 1 2 5 10 20 50 25.31
5 1 2 2 5 10 0.18
5 1 2 10 9 5 0.18
6 2 5 10 20 50 100 0.03
11 173 151 214 211 238 167 385 179 5 235 112 46.1
13 95 180 285 205 164 82 122 52 362 260 166 364 189 6.55

53 1*1+10*1+20*1+50*50
4 1*1+2*1+5*1+10*1
2 9*2
No solution.
14 112*2+151*1+385*11
4 122*1+164*1+180*1+189*1

提示

样例说明

第一组测试数据，硬币共有 $6$ 种面值，分别为 $1$ 美分、$2$ 美分、$5$ 美分、$10$ 美分、$20$ 美分、$50$ 美分，需要将 $25.31$ 美元（$2531$ 美分）兑换成硬币，具有最少硬币数量的兑换方案为：$50$ 枚硬币，$1$ 枚 $1$ 美分的硬币，$1$ 枚 $10$ 美分的硬币，$1$ 枚 $20$ 美分的硬币，$50$ 枚 $50$ 美分的硬币。

第二组测试数据，硬币共有 $5$ 种面值，但不同的只有 $4$ 种面值，分别为 $1$ 美分、$2$ 美分、$5$ 美分、$10$ 美分，需要将 $0.18$ 美元（$18$ 美分）兑换成硬币，具有最少硬币数量的兑换方案为：$4$ 枚硬币，$1$ 枚 $1$ 美分的硬币，$1$ 枚 $2$ 美分的硬币，$1$ 枚 $5$ 美分的硬币，$1$ 枚 $10$ 美分的硬币。

第三组测试数据，硬币共有 $5$ 种面值，分别为 $1$ 美分、$2$ 美分、$5$ 美分、$9$ 美分、$10$ 美分，需要将 $0.18$ 美元（$18$ 美分）兑换成硬币，具有最少硬币数量的兑换方案为：$2$ 枚硬币，$2$ 枚 $9$ 美分的硬币。

第四组数据，不存在符合要求的兑换方案，输出： No solution. 。

第五组数据，最少硬币数量为 $14$，有以下三种兑换方案：

14 112*2+151*1+385*11
14 167*1+179*2+235*1+385*10
14 173*2+179*1+235*1+385*10

按照题意，以下是字典序最小的兑换方案：

14 112*2+151*1+385*11

第六组测试数据，最少硬币数量为 $4$，有以下七种兑换方案：

4 52*2+189*1+362*1 
4 82*1+122*1+166*1+285*1 
4 95*2+180*1+285*1 
4 95*2+205*1+260*1 
4 95*1+166*1+189*1+205*1
4 122*1+164*2+205*1
4 122*1+164*1+180*1+189*1

按照题意，以下是字典序最小的兑换方案：

4 122*1+164*1+180*1+189*1

---

数据范围与约定

对于 $100\%$ 的数据，$1 \leq T \leq 400，1 \leq c \leq 100$，$1 \leq d_i \leq 400$，$0 \lt m \leq 100$。表示乘客需要兑换的纸币的总面值的实数 $m$ 有三种情形：没有小数点（是一个整数）、小数点后有一位数字、小数点后有两位数字。

在输出兑换序列时，相同的硬币面值应该合并。例如，假定正确输出为：

4 111*2+222*2

则以下输出为不符合要求的输出：

4 111*1+111*1+222*2
4 111*2+222*1+222*1
4 111*1+111*1+222*1+222*1