散列表平均查找时间

本题目标很简单：首先将一系列各不相同的正整数键值插入一张散列表，随后在表中查找另外给定的一个整数键值系列，输出平均查找时间（确定一个数字在或不在表中所需要比较的次数）。这里用到的哈希函数定义为 H(key) = key % TSize，其中 TSize 是散列表的容量。使用平方探测（仅做正向递增的探测）来解决冲突。

注意散列表的容量最好是一个素数。如果用户给出的容量不是素数，你必须将容量重新定义为比用户给定容量大的一个最小的素数。

输入格式

输入第一行给出 3 个正整数：MSize、N、M，分别是用户定义的散列表容量、要插入的键值的数量、以及要查找的键值的数量。这 3 个数都不超过 10^4。 随后第二行给出 N 个各不相同的正整数键值待插入。第三行给出 M 个正整数键值待查找。同一行中数字间以一个空格分隔，数均不超过 10^5。

输出格式

如果某个数无法插入，则在一行中输出 X cannot be inserted.，其中 X 是那个输入的数字。最后一行输出全部 M 个键值的平均查找时间，精确到小数点后 1 位。

输入样例

4 5 4
10 6 4 15 11
11 4 15 2

输出样例

15 cannot be inserted.
2.8

限制

时间限制：1000ms，内存限制：64MiB