哈德森夫人已经有一段时间没有做她著名的煎饼了,最后她决定再做一次。她最近学到了新食谱,她迫不及待地想尝试它们。这些食谱基于 n 种特殊香料。哈德森夫人将这些香料放在厨房里,放在罐子里,罐子里用 0 到 n - 1 的整数编号(每种香料都放在一个单独的罐子里)。每个罐子还刻有相应香料的价格——一些整数ai。
我们知道第 i 个煎饼配方的三个值:di、si、ci。这里di和ci是整数,si是以di为基数的数字系统中的某个整数的模式。该模式包含数字、拉丁字母(表示大于 9 的数字)和问号。二基数字系统中的数字 x 与模式 si 匹配,如果我们可以用数字和字母替换模式中的问号,从而获得数字 x(执行比较时不考虑前导零)。更正式地说:每个问号应准确地替换为一位数字或一位字母。如果我们替换所有问号后得到一个带有前导零的数字,我们可以删除这些零。例如,11 进制数字系统中的数字 40A9875 与模式“??4??987?”匹配,而数字 4A9875 则不匹配。
要按照第 i 个食谱制作煎饼,Hudson 夫人应该取出所有带有数字的罐子,这些数字在二基数字系统中的表示形式与模式 si 相匹配。配方的控制数(zi)被定义为数ci和所有采取的罐子的价格的乘积的总和。更正式地说: $$z_i = c_i + \prod_j a_j$$ (其中 j 是在 di 基数字系统中的表示与模式 si 匹配的所有此类数字)。
Hudson 夫人对控制数的兴趣不如对它们的最小质因数的兴趣。你的任务是:对于每个菜谱,我找到数字 zi 的最小素因数。如果这个除数超过100,那么你就不必求它,打印-1。
输入
第一行包含单个整数 n (1 ≤ n ≤ 104)。第二行包含香料 a0、a1、...、an - 1 的空格分隔价格,其中 ai 是整数 (1 ≤ ai ≤ 1018)。
第三行包含单个整数 m (1 ≤ m ≤ 3·104) — Hudson 夫人已经学会的食谱数量。
接下来的 m 行描述菜谱,每行一个。首先,给出一个整数 di,以十进制表示 (2 ≤ di ≤ 16)。然后在空格后面遵循 si 模式 - 长度从 1 到 30(含)的字符串,由从“0”到“9”的数字、从“A”到“F”的字母和符号“?”组成。从“A”到“F”的字母应相应地被视为从10到15的数字。保证模式的所有数字(包括字母表示的数字)严格小于di。然后,空格后面是一个整数 ci,以十进制表示 (1 ≤ ci ≤ 1018)。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数,最好使用 cin、cout、字符串或 %I64d 说明符。
输出
对于每个配方计数,控制编号除以最小质数,并将该质数打印在单行上。如果该数字大于 100,则打印 -1。
示例
输入 #1
1 1 1 2 ? 1
输出 #1
2
输入 #2
4 2 3 5 7 4 2 ?0 11 2 ?1 13 2 0? 17 2 1? 19
输出 #2
3 2 23 2
输入 #3
1 1000000000000000000 1 16 ?????????????? 1
输出 #3
-1
注意
在第一个测试中,二进制系统中的任何一位数字都匹配。罐子只有一个,其价格等于1,数c也等于1,控制数等于2。2的最小素因数是2。
在第二个测试中,有 4 个罐子,里面有 0 到 3 的数字,价格分别等于 2、3、5 和 7——前四个素数。在所有食谱中,数字应该是两位数。在第一个配方中,第二个数字始终为 0,在第二个配方中,第二个数字始终为 1,在第三个配方中,第一位必须为 0,在第四个配方中,第一个数字始终为 1。因此,控制数如下:在第一个配方中 2 × 5 + 11 = 21(最小素因数为 3),在第二个配方中 3 × 7 + 13 = 44(最小素因数为 2),在第三个配方 2 × 3 + 17 = 23 (最小素因数为 23),最后,第四个配方 5 × 7 + 19 = 54 (最小素因数为 2)。
在第三次测试中,号码应由十四位数字组成,并以十六进制数字系统记录。数字 0(单个瓶子的数量)匹配,控制数将等于 1018 + 1。该数字的最小质因数等于 101,应打印 -1。