描述

高质量的随机数生成对许多应用（尤其是密码学）至关重要。虽然放射性衰变可以提供“真随机数”，但这种方法生成速度较慢，且在某些场景中需要能在不同地点复现相同的“随机”序列。因此，人们常使用伪随机序列——看似随机但实际可预测的数列，且难以通过前几项推测后续项。

密码机械协会（ACM）设计了一种伪随机数生成算法，但不确定其可靠性，因此需要你进行测试。

算法步骤（基数为 $B$）：

1. 任选一个基数 $B$ 的初始数（种子），该数可能包含数百位。
2. 输出当前数的最后一位（最低位）作为序列的下一个元素。
3. 生成新数：从左到右计算每对相邻数字之和（和仍用基数 $B$ 表示）。例如，$B=10$ 时，数字 845 会生成 129（因为 $8+4=12$，$4+5=9$）。
4. 重复步骤 2 和 3，直到数字只剩一位，此时算法终止。

示例：
若 $B=10$，种子为 845，则生成的数列为：

• 输出 5 → 新数 129
• 输出 9 → 新数 311（$1+2=3$，$2+9=11$）
• 输出 1 → 新数 42（$3+1=4$，$1+1=2$）
• 输出 2 → 新数 6（$4+2=6$）
• 输出 6（终止）
  最终序列为 [5, 9, 1, 2, 6]。

你的任务：
给定序列的前 $L$ 项和整数 $T > L$，判断前 $T$ 项是否能由前 $L$ 项唯一确定。注意：输入可能包含无法由任何种子生成的序列。

输入

• 第一行是正整数 $N$，表示测试用例数量。
• 每个测试用例包含：
  • 第一行：基数 $B$（$2 \leq B \leq 1000$）。
  • 第二行：整数 $L$ 和序列的前 $L$ 项（每项为 $0$ 到 $B-1$ 的十进制数）。
  • 第三行：整数 $T$（$L < T \leq 100\,000$），需要预测的项的位置。

输出

对每个测试用例，输出以下之一：

1. "impossible"：无任何种子能生成该序列。
2. "unpredictable"：存在种子能生成该序列，但前 $T$ 项不能由前 $L$ 项唯一确定。
3. 第 $T$ 项的值（若可唯一确定）。

输入数据 1

3
10
5 5 9 6 7 0
7
16
4 11 7 8 4
12
2
5 0 1 1 1 0
10

输出数据 1

8
unpredictable
impossible

来源

2004 年西北欧地区竞赛