CF156E Mrs. Hudson's Pancakes

很长一段时间以来，哈德森夫人都没有制作她著名的煎饼。最终她决定再次制作。最近她学到了 $m$ 个新食谱，迫不及待地想要尝试它们。这些食谱都基于 $n$ 种特殊的香料。哈德森夫人的厨房里有这些香料，它们放在从 $0$ 到 $n-1$ 的编号罐子里（每种香料放在一个单独的罐子里）。每个罐子上还刻有对应香料的价格——一些整数 $a_i$。 我们对第 $i$ 个煎饼食谱有三个值：$d_i$，$s_i$，$c_i$。其中 $d_i$ 和 $c_i$ 是整数，$s_i$ 是以 $d_i$ 为基数的数字符号系统中的某个整数的模式串。该模式串包含数字、拉丁字母（用于表示大于九的数字）和问号。如果我们可以用数字和字母替换模式串中的问号，得到数字x（在比较时不考虑前导零），则基于 $d_i$ 的数字符号系统中的数 $x$ 与模式串 $s_i$匹配。更准确地说：每个问号应该被替换为一个数字或一个字母。如果在替换所有问号后我们得到了一个带有前导零的数字，我们可以删除这些零。例如，在基数为 $11$ 的数字符号系统中，数字 $40A9875$ 与模式串 "$??4??987?$" 匹配，而数字 $4A9875$ 则不匹配。 为了按照第 $i$ 个食谱制作薄煎饼，哈德森夫人应该拿取所有数字在 $d_i$ 进制数系统中的表示与 $s_i$ 模式串匹配的罐子。食谱的控制数字 $(z_i)$ 定义为数字 $c_i$ 和所有被拿取罐子的价格的乘积之和。更正规的说：$z_i=c_i\ + \ \prod_{j}{a_j}$（其中 $j$ 表示所有在 $d_i$ 进制数系统中的表示与 $s_i$ 模式串匹配的数字）。 相比控制数字，哈德森夫人对控制数字的最小质因子更感兴趣。你的任务是：对于每个食谱 $i$，找到数字 $z_i$ 的最小质因子。如果这个因子超过了 $100$，那么你不需要去找到它，直接输出 $-1$。

第一行包含一个整数 $n$ $(1\le n\le 10^4)$。第二行包含 $n$ 个用空格隔开的整数 $a_0,a_1,...,a_{n-1}(1\le a_i\le 10^{18})$。 第三行包含一个整数 $m \ (1\le m\le 3\cdot 10^4)$，表示哈德森夫人学习食谱的数量。 接下来 $m$ 行每行描述一个食谱。首先读入一个用十进制表示的整数 $d_i \ (2\le d_i\le 16)$。然后以一个空格隔开读入模式串 $s_i$ ——一个长度为 $1$ 到 $30$ 的字符串，包含 “0” 到 “9” 中的数字，“A” 到 “F” 中的字母 和问号 “?”。字母 “A” 到 “F” 应该被视作 $10\sim15$，保证模式串中的所有数字（包括用字母表示的数字）严格小于数字 $d_i$ 。然后以一个空格分隔，用十进制数字系统读入一个整数数字 $c_i \ (1\le c_i\le 10^{18})$。 请不要在 C++ 中使用 `%lld` 来读取或写入 64 位整数，推荐使用 `cin`、`cout`、字符串读入或者`%I64d`特定格式符。

对于每个配方，计算控制数字具有的最小素数因子并将其打印在单独的一行上。如果该素数因子大于 $\overline{100}$，则打印 $-1$。 ### **说明/提示** 在样例一中，二进制系统中的任意一位数字都匹配。罐子只有一个，其价格等于 $1$，数字 "c" 也等于 $1$，控制数字等于 $2$。$2$ 的最小质因数是 $2$。 在第二次测试中，有 $4$ 个罐子，编号从 $0$ 到 $3$，并且价格分别相等于 $2$，$3$，$5$ 和 $7$，即前四个质数。在所有配方中，数字应为两位数。在第一种配方中，第二位数字总是 $0$，在第二种配方中，第二位数字总是 $1$，在第三种配方中，第一位数字必须是 $0$，在第四种配方中，第一位数字总是 $1$。因此，控制数字如下所示：在第一种配方中，$2\times 5+11=21$（最小质因数为 $3$），在第二种配方中， $3\times 7+13=34$(原文为44，有误) （最小质因数为 $2$），在第三种配方中， $2\times 3+17=23$ （最小质因数为 $23$），最后，在第四种配方中， $5\times 7+19=54$（最小质因数为 $2$）。

In the first test any one-digit number in the binary system matches. The jar is only one and its price is equal to $ 1 $ , the number $ c $ is also equal to $ 1 $ , the control number equals $ 2 $ . The minimal prime divisor of $ 2 $ is $ 2 $ . In the second test there are $ 4 $ jars with numbers from $ 0 $ to $ 3 $ , and the prices are equal $ 2 $ , $ 3 $ , $ 5 $ and $ 7 $ correspondingly — the first four prime numbers. In all recipes numbers should be two-digit. In the first recipe the second digit always is $ 0 $ , in the second recipe the second digit always is $ 1 $ , in the third recipe the first digit must be $ 0 $ , in the fourth recipe the first digit always is $ 1 $ . Consequently, the control numbers ​​are as follows: in the first recipe $ 2×5+11=21 $ (the minimum prime divisor is $ 3 $ ), in the second recipe $ 3×7+13=44 $ (the minimum prime divisor is $ 2 $ ), in the third recipe $ 2×3+17=23 $ (the minimum prime divisor is $ 23 $ ) and, finally, in the fourth recipe $ 5×7+19=54 $ (the minimum prime divisor is $ 2 $ ). In the third test, the number should consist of fourteen digits and be recorded in a sixteen-base numeral system. Number $ 0 $ (the number of the single bottles) matches, the control number will be equal to $ 10^{18}+1 $ . The minimum prime divisor of this number is equal to $ 101 $ and you should print -1.