http://poj.org/problem?id=2061
//* @author:alpc12
/* Sample solution to D - Pseudo random numbers / Mikael Goldmann
* First count backwards to recreate the seed number
* The count forwards to get T:th number. Try using few columns to
* save space.
*/
import java.io.*;
import java.util.*;
class Main
{
static BufferedReader stdin;
int[][] tab;
public static void main(String[] ss) throws IOException
{
Reader rdr = new InputStreamReader(System.in);
stdin = new BufferedReader(rdr);
int n = Integer.parseInt(stdin.readLine());
for (int i = 1; i <= n; ++i)
(new Main()).solve(i);
}
void solve(int casenum) throws IOException
{
int i,j;
int B = Integer.parseInt(stdin.readLine());
String[] tok =stdin.readLine().split("[ ]+");
int L = Integer.parseInt(tok[0]);
int T = Integer.parseInt(stdin.readLine());
int ncol=5;
int[] vals = new int[L];
for (i=1; i <= L; ++i)
vals[i-1] = Integer.parseInt(tok[i]);
boolean ok=false;
while(!ok) {
ok = true;
try{
ncol *= 2;
tab = newtab(L,ncol);
for (i = 0; i < L; ++i)
tab[i][0] = vals[i];
for(i = L-1; i > 0; --i)
if (! explain(tab,i, ncol, B)) {
System.out.println("impossible");
return;
}
}
catch(ArrayIndexOutOfBoundsException e) {
ok = false;
// Retry, doubling number of columns
}
}
// Now tab[0] contains the seed numbers digits
int ncol1=ncol+1; // One extra column
/* Try finding values on the T:th row
* If we fail and truncated any row, retry using
* twice as many columns
*/
int k;
while (true) {
boolean fullrow = false; // no overflowing row yet
int[][] v = new int[2][ncol1];
for (i = 0; i < ncol; ++i)
v[0][i] = tab[0][i];
for (i = ncol; i < ncol1; ++i)
v[0][i] = -1;
int[] a,b=null;;
int tmp;
ok = true;
for (k = 1; k < T; ++k) {
a = v[1-(k&1)];
b = v[k&1];
for (i = 0; i < ncol1; ++i) b[i] = -1;
for (i = 1, j = 0; j < ncol1 && i < ncol1; ++i) {
if (a[i] == -1) break;
tmp = a[i-1]+a[i];
if (tmp < B) b[j++] = tmp;
else {
b[j++] = tmp-B;
if (j < ncol1) b[j++] = 1;
}
}
if (j == ncol1) fullrow=true;
if (b[0] == -1) {
ok = false;
break;
}
}
if (ok) {
System.out.println(b[0]);
return;
}
else if(!fullrow) {
System.out.println("unpredictable");
return;
}
ncol1 *=2;
}
}
int[][] newtab(int r, int c)
{
int[][] t = new int[r][c];
int i,j;
for (i=0; i < r; ++i)
for (j = 0; j < c; ++j)
t[i][j] = -1;
return t;
}
/* explain() computes row (i-1) from row i
* Returns false if impossible. Used to calculate seed
* from the given sequence
*/
boolean explain(int[][] tab, int r, int ncol, int B)
{
int[] s = new int[ncol];
int i,j;
for (i=0; i < ncol; ++i) s[i] = -1;
i=0;
j=1;
int s1,t1;
while (i < ncol && tab[r][i] != -1) {
tab[r-1][j] = (B + tab[r][i] - tab[r-1][j-1]) % B;
s1 = tab[r-1][j] + tab[r-1][j-1];
++i;
++j;
if (s1 >= B) {
if (tab[r][i] != -1 && tab[r][i] != 1) return false;
++i;
}
}
return true;
}
}