F. 十六进制的异或
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

题目背景

蔡光在学数字逻辑！

题面描述

在十进制下，$$$A$$$ $$$xor$$$ $$$B$$$ 是一个很简单的问题，但当蔡光计算到 $$$(1234)_H \bigoplus (5678)_H$$$ 这样的问题时却摸不到头脑。

定义十六进制下的 $$$\bigoplus$$$ 为 不进位加法 ，例如 $$$3_H \bigoplus 4_H = 7_H$$$，$$$A_H \bigoplus B_H = 5_H$$$。

蔡光将给出 $$$n$$$ 个不同的十六进制数 $$$a_i$$$ 与 $$$q$$$ 次询问。

对于每次询问，蔡光将给你一个十进制正整数 $$$x$$$ ，他想请你找出一个正整数 $$$i$$$ ，使得 $$$x$$$ 与 $$$a_i$$$ 十六进制下异或出的值在十进制下最大，并输出这个下标 $$$i$$$ ，作为你的答案。

Input

一行两个整数 $$$n,q$$$，代表数字个数。$$$(1 \leq n,q \leq 10^5)$$$

接下来一行包含 $$$n$$$ 个不同的合法十六进制非负数 $$$a_1, ..., a_n $$$。每个数的长度不超过 $$$20$$$。大写字母 'A' $$$\sim$$$ 'F' 分别代表十进制下的 $$$10$$$ $$$\sim$$$ $$$15$$$。

接下来 $$$q$$$ 行，每行包含一个合法的十进制正整数 $$$x$$$ , 请回答蔡光的问题。$$$(1 \leq x \leq 10^{18})$$$

Output

输出 $$$q$$$ 行，每行一个整数 $$$ans$$$，代表上述问题你的答案。

Examples
Input
3 3
1 2 3
14
15
16
Output
1
3
3
Input
3 3
ABC BCA FFF
1347
837
0
Output
1
2
3