9833번 - Sequence 다국어

The task is to predict sequences according to the easiest underlying law which applies. For this task, the following three laws are considered. Every integer in the sequences is in the range [0, 1, . . ., m−1] where m is a parameter given at the input; m is never larger than 10000.

Eventually constant sequences: An eventually constant sequence is a sequence a₀ a₁ . . . a_n . . . such that there is a number d with a_n = a_d for all n ≥ d; the least such number d is called the degree of the sequence. For example, 0 8 6 6 6 . . . is an eventually constant sequence of degree 2.

Periodic sequences: A periodic sequence is a sequence given by a seed a₀ a₁ . . . a_d such that for all n > d it holds that a_n = a_n−d−1. The degree d of a periodic sequence is the least number d such that a₀ a₁ . . . a_d is a seed of the sequence. For example, 1 2 3 4 1 2 3 4 1 2 . . . is a degree-3 periodic sequence with seed 1 2 3 4.

Polynomial sequences: A polynomial sequence modulo m of degree d is a sequence a₀ a₁ . . . a_n . . . generated from an integer-valued polynomial of degree d. For example, 0 0 1 3 6 10 15 1 . . . is a degree-2 polynomial modulo 20 generated by a_n = (n²/2 − n/2) mod 20. An alternative approach to define a polynomial sequence is as follows. A sequence a₀ a₁ . . . a_n . . . is a polynomial sequence modulo m of degree d if it is a constant sequence (i.e., a_n = a₀ for all n) with degree d = 0 or it is a sequence derived from another nonzero sequence b₀ b₁ . . . of degree d−1 such that a_n+1 = (a_n + b_n) mod m for all n. The second approach enables us to build a prediction method without using multiplications and divisions. (Note: x mod y equals the reminder r when x is divided by y. We assume 0 ≤ r < y.)

Note that all three concepts are related as the constant sequences are just the sequences of degree 0 of any of these three concepts.

Our task is to predict the concept of least degree which matches the data. For example, suppose we want to predict a₃ for a periodic sequence with a₀ = 0, a₁ = 1, and a₂ = 0. Then, we predict a₃ = 1 since the data follows the periodic sequence of degree 1 with seed 0 1. Note that we should not predict a₃ = 0 which follows the periodic sequence of degree 2 with seed 0 1 0.

Furthermore, some prediction task asks to identify, among the concepts of eventually constant, periodic and polynomial sequences, the concept that gives the lowest degree and then to predict the next value along that concept. All prediction tasks given admit a unique solution.

Your program must read from the standard input the following data. Each task is given in one of the following formats: “Ec m a0 a1 . . . an−1” (for eventually constant sequences), “Pe m a0 a1 . . . an−1” (for periodic sequences), “Po m a0 a1 . . . an−1” (for polynomial sequences), “Se m a0 a1 . . . an−1” (for general prediction tasks where the program has to chose the adequate concept with the lowest degree). There can be several prediction tasks which are separated by semicolons and a full stop follows the last prediction task. The number n is at most 90 and the number m is at most 10000. Also, for every a_i, 1 ≤ a_i ≤ m.

For each input sequence, exactly one number should be output to standard output; this number has to be the next element in the sequence which matches the description.