Pseudo-random Numbers

Many applications need good random numbers, cryptography most of all. Radioactive decay is sometimes used as a source of true randomness, but it delivers numbers slowly. Many applications also have to reproduce the same "random" sequence in two different places. A pseudo-random sequence is used instead. Such a sequence is not random, yet it is very hard to tell apart from a truly random one, and it should be hard to predict: knowing the first few elements should not make it easy to work out a later element nobody has seen yet.

The Association of Cryptographic Machinery (ACM) designed an algorithm that produces pseudo-random sequences, and nobody there knows how good it really is, so they want you to test it.

Every element the algorithm produces is an integer between $0$ and $B - 1$ inclusive. The algorithm works as follows.

1. Start with any seed written in base $B$. The seed is a nonempty string of base $B$ digits, it may begin with zeros, and it can be hundreds of digits long.
2. Output the last digit (the least significant one) as the next element of the sequence.
3. Build a new number by writing down the sums of neighbouring digits from left to right. Each sum is written in base $B$, so a sum of $B$ or more takes two digits. With $B = 10$ the number $845$ becomes $129$, because $8 + 4 = 12$ and $4 + 5 = 9$.
4. Repeat steps 2 and 3 until the number has a single base $B$ digit. That digit is the last element of the sequence and the algorithm stops.

With $B = 10$ and the seed $845$ the numbers are $845$, $129$, $311$ ($1 + 2 = 3$ and $2 + 9 = 11$), $42$ ($3 + 1 = 4$ and $1 + 1 = 2$) and $6$ ($4 + 2 = 6$). The last one has a single digit, so the algorithm stops there. The pseudo-random digits it produced are $5$, $9$, $1$, $2$ and $6$.

You test the generator like this. You are given the first $L$ elements the generator produced and an integer $T > L$. Decide whether the first $L$ elements completely determine the first $T$ elements. If some seed that produces the given $L$ elements yields a sequence of fewer than $T$ elements, then the first $T$ elements are not determined. The ACM also slipped in a few impossible sequences that no seed can produce, to see how robust your test is.

The first line has one positive integer $N$, the number of test cases. Each test case takes three lines. The first line has the base $B$ ($2 \le B \le 1000$). The second line has an integer $L$ ($1 \le L \le 100$) followed by the first $L$ elements of some sequence; the elements are written in base 10 and lie between $0$ and $B - 1$ inclusive. The third line has the integer $T$ ($L < T \le 100000$), the position of the element to predict.

For each test case print one line:

• impossible if no seed produces the given sequence;
• unpredictable if some seed produces the given sequence but the first $L$ elements do not completely determine the first $T$ elements;
• otherwise the $T$-th element of the sequence, written in base 10.