수열 예측

주어진 수열에 들어맞는 가장 단순한 법칙을 찾아 다음 항을 예측한다. 여기서 다루는 법칙은 세 가지다. 수열의 원소는 모두 $0$ 이상 $m-1$ 이하의 정수이고, $m$은 입력으로 주어지며 $10000$을 넘지 않는다.

결국 상수가 되는 수열. 수열 $a_0\ a_1\ \dots\ a_n\ \dots$ 에서 $n \ge d$인 모든 $n$이 $a_n = a_d$를 만족하는 수 $d$가 있으면, 이 수열은 결국 상수가 되는 수열이다. 그런 $d$ 중 가장 작은 값이 이 수열의 차수다. 예를 들어 $0\ 8\ 6\ 6\ 6\ \dots$ 는 차수가 $2$인, 결국 상수가 되는 수열이다.

주기 수열. 씨앗 $a_0\ a_1\ \dots\ a_d$ 로 정해지고 $n > d$인 모든 $n$이 $a_n = a_{n-d-1}$을 만족하는 수열을 주기 수열이라 한다. 주기 수열의 차수 $d$는 $a_0\ a_1\ \dots\ a_d$ 가 그 수열의 씨앗이 되는 가장 작은 $d$다. 예를 들어 $1\ 2\ 3\ 4\ 1\ 2\ 3\ 4\ 1\ 2\ \dots$ 는 씨앗이 $1\ 2\ 3\ 4$이고 차수가 $3$인 주기 수열이다.

다항 수열. $m$을 법으로 하는 차수 $d$의 다항 수열은 차수가 $d$인 정수값 다항식이 만들어 내는 수열 $a_0\ a_1\ \dots\ a_n\ \dots$ 이다. 예를 들어 $0\ 0\ 1\ 3\ 6\ 10\ 15\ 1\ \dots$ 은 $a_n = (n^2/2 - n/2) \bmod 20$ 이 만드는, $20$을 법으로 하는 차수 $2$의 다항 수열이다. 다항 수열은 이렇게 정의할 수도 있다. 수열 $a_0\ a_1\ \dots$ 가 모든 $n$에서 $a_n = a_0$인 상수 수열이면 차수 $0$의 다항 수열이고, 항이 전부 $0$은 아닌 차수 $d-1$의 다른 수열 $b_0\ b_1\ \dots$ 에서 모든 $n$이 $a_{n+1} = (a_n + b_n) \bmod m$ 을 만족하도록 얻어지면 차수 $d$의 다항 수열이다. 두 번째 정의를 쓰면 곱셈도 나눗셈도 없이 예측 방법을 세울 수 있다. ($x \bmod y$ 는 $x$를 $y$로 나눈 나머지 $r$이고, $0 \le r < y$다.)

상수 수열은 세 법칙 어느 쪽에서 보아도 차수가 $0$인 수열이다.

할 일은 데이터에 들어맞는 법칙 중 차수가 가장 작은 것을 골라 그 법칙대로 다음 항을 예측하는 것이다. $a_0 = 0$, $a_1 = 1$, $a_2 = 0$인 주기 수열에서 $a_3$을 예측한다고 하자. 이 데이터는 씨앗이 $0\ 1$이고 차수가 $1$인 주기 수열을 따르므로 $a_3 = 1$로 예측한다. 씨앗이 $0\ 1\ 0$이고 차수가 $2$인 주기 수열을 따라 $a_3 = 0$으로 예측하면 안 된다.

결국 상수가 되는 수열, 주기 수열, 다항 수열 가운데 차수가 가장 작아지는 법칙을 직접 골라야 하는 과제도 있다. 주어지는 예측 과제의 답은 모두 하나로 정해진다.

입력은 예측 과제 여러 개로 이루어진다. 각 과제는 다음 네 형식 중 하나다.

• Ec $m\ a_0\ a_1\ \dots\ a_{n-1}$: 결국 상수가 되는 수열
• Pe $m\ a_0\ a_1\ \dots\ a_{n-1}$: 주기 수열
• Po $m\ a_0\ a_1\ \dots\ a_{n-1}$: 다항 수열
• Se $m\ a_0\ a_1\ \dots\ a_{n-1}$: 차수가 가장 작은 법칙을 직접 골라야 하는 과제

과제와 과제 사이는 세미콜론(;)으로 구분하고, 마지막 과제 뒤에는 마침표(.)가 온다. 한 과제를 이루는 토큰이 여러 줄에 걸쳐 나올 수도 있다.

$n$은 최대 $90$, $m$은 최대 $10000$이고, 모든 $i$에서 $0 \le a_i \le m-1$이다.

각 예측 과제마다 설명에 맞는 다음 항을 정수 하나로 한 줄에 출력한다.