题目描述

设有一个以 $p$ 为底的进位制，其中给出了 $n$ 个两两不同的数字。

要求把这 $n$ 个数字每个恰好使用一次，构造出若干组方案。每组方案由 $k$ 个 $p$ 进制非负整数构成，这些数都不允许有前导零。其中第一个数有 $d_1$ 位，第二个数有 $d_2$ 位，……，第 $k$ 个数有 $d_k$ 位，并且满足：

$$d_1+d_2+\cdots+d_k=n$$

对于每一组方案，考虑这 $k$ 个数的乘积。

请编写程序 maxprod，求所有可能方案中乘积的最大值。

输入格式

标准输入共三行：

• 第 1 行：三个十进制自然数 $p,n,k$，分别表示所讨论进位制的底数、数字个数，以及每组方案中数的个数；
• 第 2 行：给出 $n$ 个互不相同的 $p$ 进制数字，数字之间用空格分隔。
  对于值在 $0$ 到 $9$ 的数字，使用通常的数字字符表示；对于更大的值，则依次使用大写英文字母 A 到 Z 表示，其中 A 表示 $10$，B 表示 $11$，依此类推；
• 第 3 行：给出 $k$ 个十进制自然数 $d_1,d_2,\ldots,d_k$，表示每组方案中对应各数的位数。

输出格式

输出一行，一个 $p$ 进制数，表示按题意构造时所能得到的最大乘积。

数据范围

• $2 \le p \le 36$；
• $n>1$；
• $d_1+d_2+\cdots+d_k=n$；
• 在 $20\%$ 的测试中，$p=10$；
• 在 $50\%$ 的测试中，$p \le 16$。

样例

输入

11 9 3
A 3 2 4 8 5 7 6 9
4 2 3

输出

719603A68

样例说明

最大乘积（以 $11$ 进制表示）为：

$$8742_{11} \times A5_{11} \times 963_{11} = 719603A68_{11}$$