시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

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 a0 a1 . . . an . . . such that there is a number d with an = ad 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 a0 a1 . . . ad such that for all n > d it holds that an = an−d−1. The degree d of a periodic sequence is the least number d such that a0 a1 . . . ad 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 a0 a1 . . . an . . . 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 an = (n2/2 − n/2) mod 20. An alternative approach to define a polynomial sequence is as follows. A sequence a0 a1 . . . an . . . is a polynomial sequence modulo m of degree d if it is a constant sequence (i.e., an = a0 for all n) with degree d = 0 or it is a sequence derived from another nonzero sequence b0 b1 . . . of degree d−1 such that an+1 = (an + bn) 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 a3 for a periodic sequence with a0 = 0, a1 = 1, and a2 = 0. Then, we predict a3 = 1 since the data follows the periodic sequence of degree 1 with seed 0 1. Note that we should not predict a3 = 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 ai, 1 ≤ ai ≤ 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.

예제 입력 1

Pe 5 0 1 2 0 1;
Ec 2 0 1 1 1;
Po 100 0 1 4 9 16;
Se 50 1 1 0 1.

예제 출력 1

2
1
25
1