Statement
我想创建一个在线扑克网站。这类系统中一个非常重要的组件是随机数生成器。它需要足够快且足够随机。以下是我想到的一个折中方案。我需要一种生成长度至多为 D 的随机数的方法。我的计划是选择一个质数 P ≤ 10。我还要选择非负整数 A 和 B。最后,我会选择一个介于0和P-1之间(含)的整数种子 S。
为了输出我的伪随机数序列,我将首先输出 S,然后按如下方式计算 S 的新值:
S := (A*S + B) mod P.
然后我将输出 S 的新值作为序列中的下一个数,并使用相同的公式再次更新 S。我可以重复任意多次。
你认为这是一个好的随机数生成器吗?你能编写一个程序,接受由我的随机数生成器生成的序列中的 K 个连续元素,并打印该序列的下一个元素吗?
Input
输入的第一行给出测试用例的数量 T。接下来是 T 个测试用例。每个测试用例以一行开始,包含 D 和 K。下一行包含由上述类型的随机数生成器生成的 K 个连续元素。
### 数据范围
- 1 ≤ T ≤ 100.
- 1 ≤ K ≤ 10.
- K 个整数将是连续元素,属于
- 由上述类型的随机数生成器生成的
- 序列。
- 1 ≤ D ≤ 4.
- 1 ≤ D ≤ 6.
Output
按测试用例顺序逐个输出答案。对于每个测试用例,输出一行,包含 y,其中 y 是序列中的下一个数,或者如果答案不明确,则是字符串 "I don't know."。
Examples
Input
3
2 10
0 1 2 3 4 5 6 7 8 9
3 1
13
1 5
6 6 6 6 6Output
10
I don't know.
6Constraints
- Time limit: 10000 ms
- Memory limit: 1048576 KB
- Tag: math
- Tag: number-theory