I. 简易哈希表

引

考虑如下这个问题：

给定 $n$ 个非负整数 $a_1,a_2,\dots,a_n$，你需要回答 $q$ 次询问，每次询问查询 $x$ 是否在这 $n$ 个非负整数里面出现。

数据范围：$1\le n,q\le 10^6,0\le a_i<2^{64}$.

结合所学知识，不难想到以下两种做法：

• 方法一：将所有数储存在一个链表里面，每次询问的时候从头到尾枚举里面的每一个元素，看看是否和查询的数 $x$ 相同。这个方法的时间复杂度为 $\mathcal O(nq)$，无法解决较大的数据规模。
• 方法二：定义数组 $\texttt{occ[val]}$ 表示 $\texttt{val}$ 是否出现过，每次询问 $x$ 时，访问 $\texttt{occ[x]}$ 可以直接得到所需的信息。该算法的时间复杂度为 $\mathcal O(n+q)$，然而，若 $a$ 的值域过大（比如达到了 $10^{18}$ 的量级），就需要声明一个长度为 $10^{18}$ 的数组，将需要消耗 $10^{18}\times 4 \text{ B}\approx 3.6\times 10^6\text{ TB}$ 的空间，显然无法接受。

如果保证数列 $a$ 里的每一个元素都在值域内 $\color{red}均匀随机$ 地生成，该问题可以被一个较为巧妙的做法解决。

观察这 $n$ 个数的最后四位数码，容易发现，若 $a$ 里的每个元素都随机生成，那么 $a_i$ 的最后四位数码在 $[0,10^4)$ 中也应该是均匀分布的，如果把 $a$ 中所有最后四位全是 $0$ 的存成一个链表，那么这个链表的长度期望为 $\dfrac{n}{10^4}$。对于其他最后四位的组合也是同理。

当查询一个值 $x$ 是否在 $a$ 中出现时，也就不需要像方法一里面那样枚举 $n$ 个数，而是只需要看跟 $x$ 最后四位相同的数即可。

题面

给定 $n$ 个非负整数 $a_1,a_2,\dots,a_n$，你需要回答 $q$ 次询问，每次询问查询 $x$ 是否在这 $n$ 个非负整数里面出现。

若 $x$ 出现，输出 $x$ 在数列最后一次出现的位置，否则输出 $\texttt 0$。

第一行两个正整数 $n,q$（$1\le n,q\le 10^6$）.

接下来一行 $n$ 个非负整数 $a_1,a_2,\dots,a_n$（$0\le a_i<2^{64}$），描述这 $n$ 个数.

最后 $q$ 行每行一个非负整数 $x$ （$0\le x<2^{64}$），描述每次询问。

保证 $n$ 个非负整数是在 $[0,2^{64})$ 中均匀随机生成的。

输出 $q$ 行，回答每次询问。

对于每次询问，若 $x$ 出现，输出 $x$ 在数列最后一次出现的位置，否则输出 $\texttt 0$。

样例 1

输入

6 6
1 1 4 5 1 4
3
5
0
2
1
4

输出

0
4
0
0
5
6

$\texttt{long long}$ 只能存储 $[-2^{63},2^{63})$ 内的整数。为了更愉快地解决本题，推荐使用 $\texttt{unsigned long long}$ 数据类型，其可以存储 $[0,2^{64})$ 内的整数，定义和输入输出等操作语句与 $\texttt{long long}$ 几乎相同。

本题输入输出量较大，建议关闭 I/O 同步流，从而减少输入输出所花费的时间。

最小示范单元如下：

int main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    //在 main 函数里加上上述两行语句，可以加快输入输出的速度.

    int x;
    cin>>x;//faster
    cout<<x<<'\n';
    //注意：尽量避免使用 endl 进行换行，而是直接输出换行符 '\n'.

    return 0;
}