### 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 Sn = Sn-1+Sn-2 (mod P). A more complicated one is Sn = Sn-11*Sn-2 + Sn-1 + 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,P-1]. You will be given the K sequential random numbers for K in [M,min(1000000,3*MD)]. 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 1-9 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 non-example test cases.

### Examples

0)

 `"1"`
`Returns: ""`
 P = 101 N = 4 D = 2 M = 5 K = 50
1)

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

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

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

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

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

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

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

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

 `"18"`
`Returns: ""`
 P = 39317 N = 169 D = 2 M = 26 K = 1485

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10201

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13569&pm=10201

Unknown