CF156E.Mrs. Hudson's Pancakes

Mrs. Hudson hasn't made her famous pancakes for quite a while and finally she decided to make them again. She has learned m new recipes recently and she can't wait to try them. Those recipes are based on n special spices. Mrs. Hudson has these spices in the kitchen lying in jars numbered with integers from 0 to n - 1 (each spice lies in an individual jar). Each jar also has the price of the corresponding spice inscribed — some integer a__i.

We know three values for the i-th pancake recipe: d__i, s__i, c__i. Here d__i and c__i are integers, and s__i is the pattern of some integer written in the numeral system with radix d__i. The pattern contains digits, Latin letters (to denote digits larger than nine) and question marks. Number x in the d__i-base numeral system matches the pattern s__i, if we can replace question marks in the pattern with digits and letters so that we obtain number x (leading zeroes aren't taken into consideration when performing the comparison). More formally: each question mark should be replaced by exactly one digit or exactly one letter. If after we replace all question marks we get a number with leading zeroes, we can delete these zeroes. For example, number 40A9875 in the 11-base numeral system matches the pattern "??4??987?", and number 4A9875 does not.

To make the pancakes by the i-th recipe, Mrs. Hudson should take all jars with numbers whose representation in the d__i-base numeral system matches the pattern s__i. The control number of the recipe (z__i) is defined as the sum of number c__i and the product of prices of all taken jars. More formally: (where j is all such numbers whose representation in the d__i-base numeral system matches the pattern s__i).

Mrs. Hudson isn't as interested in the control numbers as she is in their minimum prime divisors. Your task is: for each recipe i find the minimum prime divisor of number z__i. If this divisor exceeds 100, then you do not have to find it, print -1.

胡德森太太已经很久没有做她著名的煎饼了，终于她决定再次制作。最近她学会了 $ m $ 种新食谱，迫不及待想尝试它们。这些食谱基于 $ n $ 种特殊香料。胡德森太太的厨房里备有这些香料，分别装在编号为 $ 0 $ 到 $ n-1 $ 的罐子中（每种香料单独存放于一个罐子）。每个罐子上还标有对应香料的价格——一个整数 $ a_i $。

对于第 $ i $ 种煎饼食谱，我们已知三个值：$ d_i $、$ s_i $、$ c_i $。其中 $ d_i $ 和 $ c_i $ 是整数，而 $ s_i $ 是某个整数在 $ d_i $ 进制下表示的模式串。该模式串由数字、拉丁字母（用于表示大于 9 的数码）以及问号组成。若将模式串 $ s_i $ 中的所有问号替换为数码或字母后，可得到整数 $ x $ 在 $ d_i $ 进制下的表示（忽略前导零），则称整数 $ x $ 在 $ d_i $ 进制下的表示匹配模式串 $ s_i $。更准确地说：每个问号必须被恰好替换为一个数码或一个字母；替换完成后若所得数字串含有前导零，则允许将其全部删除。例如，在 11 进制下，数字 $ 40A9875 $ 匹配模式串 "??4??987?"，而数字 $ 4A9875 $ 不匹配。

要按第 $ i $ 种食谱制作煎饼，胡德森太太需取走所有编号 $ j $ 满足其在 $ d_i $ 进制下的表示匹配模式串 $ s_i $ 的香料罐。该食谱的控制数（记作 $ z_i $）定义为 $ c_i $ 与所有被取走罐子中香料价格之积的和。更正式地：

（其中 $ j $ 遍历所有满足其在 $ d_i $ 进制下的表示匹配模式串 $ s_i $ 的编号）

胡德森太太对控制数本身兴趣不大，而更关心其最小质因数。你的任务是：对每个食谱 $ i $，求出 $ z_i $ 的最小质因数；若该最小质因数大于 100，则无需具体求出，直接输出 -1。

The first line contains the single integer n (1 ≤ n ≤ 104). The second line contains space-separated prices of the spices _a_0, _a_1, ..., a__n - 1, where a__i is an integer (1 ≤ a__i ≤ 1018).

The third line contains the single integer m (1 ≤ m ≤ 3·104) — the number of recipes Mrs. Hudson has learned.

Next m lines describe the recipes, one per line. First you are given an integer d__i, written in the decimal numeral system (2 ≤ d__i ≤ 16). Then after a space follows the s__i pattern — a string from 1 to 30 in length, inclusive, consisting of digits from "0" to "9", letters from "A" to "F" and signs "?". Letters from "A" to "F" should be considered as digits from 10 to 15 correspondingly. It is guaranteed that all digits of the pattern (including the digits that are represented by letters) are strictly less than d__i. Then after a space follows an integer c__i, written in the decimal numeral system (1 ≤ c__i ≤ 1018).

Please do not use the %lld specificator to read or write 64-bit integers in С++, in is preferred to use cin, cout, strings or the %I64d specificator instead.

第一行包含一个整数 $n$（$1 \leq n \leq 10^4$）。
第二行包含 $n$ 个由空格分隔的香料价格 $a_0, a_1, \dots, a_{n-1}$，其中每个 $a_i$ 是一个整数（$1 \leq a_i \leq 10^{18}$）。

第三行包含一个整数 $m$（$1 \leq m \leq 3 \cdot 10^4$）—— 表示哈德森夫人已掌握的食谱数量。

接下来的 $m$ 行描述这些食谱，每行一条。首先给出一个整数 $d_i$（以十进制表示，满足 $2 \leq d_i \leq 16$）；随后是一个空格；接着是字符串模式 $s_i$，其长度为 $1$ 至 $30$（含端点），由字符 "0"–"9"、字母 "A"–"F" 及符号 "?" 组成。其中字母 "A"–"F" 分别代表数字 $10$–$15$。保证该模式中所有数字（包括由字母表示的数字）均严格小于 $d_i$；再随后是一个空格；最后是一个整数 $c_i$（以十进制表示，满足 $1 \leq c_i \leq 10^{18}$）。

在 C++ 中，请勿使用 %lld 格式说明符读写 64 位整数；推荐使用 cin、cout、string 或 %I64d 格式说明符。

For each recipe count by what minimum prime number the control number is divided and print this prime number on the single line. If this number turns out larger than 100, print -1.

对每个食谱，计算其控制数能被整除的最小质数，并在单独一行输出该质数。若该质数大于 100，则输出 -1。

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 1018 + 1. The minimum prime divisor of this number is equal to 101 and you should print -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 = 44$（最小质因数为 $2$），第三个配方为 $2 \times 3 + 17 = 23$（最小质因数为 $23$），第四个配方为 $5 \times 7 + 19 = 54$（最小质因数为 $2$）。

在第三个测试中，该数字应由十四位组成，并以十六进制表示。数字 $0$（即唯一瓶子的编号）满足条件，此时校验数为 $10^{18} + 1$。该数的最小质因数为 $101$，因此应输出 $-1$。