Sequence Prediction

Predict the next term of a sequence by finding the simplest law that fits it. Three laws are considered here. Every element of a sequence is an integer between $0$ and $m-1$, where $m$ is given in the input and never exceeds $10000$.

Eventually constant sequences. A sequence $a_0\ a_1\ \dots\ a_n\ \dots$ is eventually constant if there is a number $d$ such that $a_n = a_d$ for every $n \ge d$. The least such $d$ is the degree of the sequence. For example, $0\ 8\ 6\ 6\ 6\ \dots$ is an eventually constant sequence of degree $2$.

Periodic sequences. A periodic sequence is given by a seed $a_0\ a_1\ \dots\ a_d$ such that $a_n = a_{n-d-1}$ for every $n > d$. The degree $d$ of a periodic sequence is the least $d$ for which $a_0\ a_1\ \dots\ a_d$ is a seed of the sequence. For example, $1\ 2\ 3\ 4\ 1\ 2\ 3\ 4\ 1\ 2\ \dots$ is a periodic sequence of degree $3$ with seed $1\ 2\ 3\ 4$.

Polynomial sequences. A polynomial sequence modulo $m$ of degree $d$ is a sequence $a_0\ a_1\ \dots\ a_n\ \dots$ generated by an integer-valued polynomial of degree $d$. For example, $0\ 0\ 1\ 3\ 6\ 10\ 15\ 1\ \dots$ is a polynomial sequence modulo $20$ of degree $2$, generated by $a_n = (n^2/2 - n/2) \bmod 20$. A second definition works too. A sequence $a_0\ a_1\ \dots$ is a polynomial sequence modulo $m$ of degree $d$ if it is a constant sequence ($a_n = a_0$ for every $n$) with $d = 0$, or if it comes from another sequence $b_0\ b_1\ \dots$ of degree $d-1$ whose terms are not all $0$, with $a_{n+1} = (a_n + b_n) \bmod m$ for every $n$. The second definition gives a prediction method that uses neither multiplication nor division. (Here $x \bmod y$ is the remainder $r$ of $x$ divided by $y$, with $0 \le r < y$.)

A constant sequence has degree $0$ under all three laws.

The task is to pick the law of least degree that matches the data and predict the next term along it. Say you want to predict $a_3$ of a periodic sequence with $a_0 = 0$, $a_1 = 1$ and $a_2 = 0$. The data follows the periodic sequence of degree $1$ with seed $0\ 1$, so the prediction is $a_3 = 1$. Predicting $a_3 = 0$, which follows the degree $2$ periodic sequence with seed $0\ 1\ 0$, is wrong.

Some tasks ask you to choose, among eventually constant sequences, periodic sequences and polynomial sequences, the law that gives the lowest degree, and then to predict the next value along that law. Every prediction task given admits a unique solution.

The input holds several prediction tasks. Each task comes in one of four formats.

• Ec $m\ a_0\ a_1\ \dots\ a_{n-1}$: eventually constant sequence
• Pe $m\ a_0\ a_1\ \dots\ a_{n-1}$: periodic sequence
• Po $m\ a_0\ a_1\ \dots\ a_{n-1}$: polynomial sequence
• Se $m\ a_0\ a_1\ \dots\ a_{n-1}$: your program picks the law of lowest degree itself

Tasks are separated by a semicolon ;, and a full stop . follows the last one. The tokens of a single task may be spread over several lines.

$n$ is at most $90$, $m$ is at most $10000$, and $0 \le a_i \le m-1$ for every $i$.

For each prediction task print one integer on its own line: the next element of the sequence that matches the description.