Problem Statement 
 In this problem your task is to break a pseudorandom number generator given its last K outputs. Each `random' number will be generated as a function of the previous M `random' numbers, for some M. After the function is evaluated, the result is taken modulo a prime P, and that is the output. For instance, a simple generator function would be S_{n} = S_{n1}+S_{n2} (mod P). A more complicated one is S_{n} = S_{n11}*S_{n2} + S_{n1} + 1 (mod P). In general we will consider polynomials functions of the last M numbers. Your task is to write a method crack that takes a int[] S, a int, M, an int P, and returns your best guess for the next M numbers output by the generator.
The prime, P will be between 101 and 40000, inclusive. M will be chosen as floor(rand()*rand()*996)+5, where rand() is a uniform random number in [0,1].
The polynomial will be generated by first picking D, the maximum degree as 1, 2, or 3. The number of terms will then be chosen in [2,min(200,1+M+(D>1?M(M+1)/2)+(D>2?M(M+1)(M+2)/6)], and each term will be generated with a degree in [0,D]. After the degree d is chosen, d (not necessarily distinct) previous random numbers (offsets) are selected as the components of the term. If this generates a term which has already been generated, the process is repeated (so, degree 0 will only occur once, for instance). After the variables are chosen, the coefficient is chosen in [0,P1]. You will be given the K sequential random numbers for K in [M,min(1000000,3*M^{D})]. The random number generator will be initialized with M random values, and then run for K+100*M iterations, of which you will be given the final K.
All random choices are uniform and independent.
Your score will be the number of the M entries that are correct. Your overall score will simply be the sum of your individual scores.
You can download the source code and class files to generate a sequence of random numbers. To run, simply enter 'java LaggedGenerator <seed>'. The output will be the M initial values, followed by an asterisk, followed by 100M random values, followed by an asterisk, followed by K random values, followed by an asterisk, and finally the M values to predict. The seeds for the examples are 19 and 18, in order. 

Definition 
 Class:  LaggedGenerator  Method:  crack  Parameters:  int[], int, int  Returns:  int[]  Method signature:  int[] crack(int[] S, int P, int M)  (be sure your method is public) 




Notes 
  The time limit is 30 seconds. 
  The memory limit is 1024M. 
  In the examples, N is the number of terms in the polynomial. 
  There are 100 nonexample test cases. 

Examples 
0)  
  Returns: ""  P = 101
N = 4
D = 2
M = 5
K = 50



1)  
  Returns: ""  P = 36299
N = 7
D = 1
M = 16
K = 44



2)  
  Returns: ""  P = 23789
N = 177
D = 3
M = 102
K = 668069



3)  
  Returns: ""  P = 13687
N = 62
D = 2
M = 155
K = 4147



4)  
  Returns: ""  P = 28403
N = 26
D = 1
M = 25
K = 40



5)  
  Returns: ""  P = 17257
N = 19
D = 3
M = 611
K = 682883



6)  
  Returns: ""  P = 21481
N = 51
D = 1
M = 115
K = 193



7)  
  Returns: ""  P = 24281
N = 180
D = 2
M = 211
K = 125395



8)  
  Returns: ""  P = 27847
N = 127
D = 1
M = 565
K = 928



9)  
  Returns: ""  P = 39317
N = 169
D = 2
M = 26
K = 1485


