P5379 [THUPC 2019] An Unforgettable Problem Title

Now there is an integer sequence $S$ of length $N$ (indexed from $0$). Alice and Bob play a game on this sequence. The game proceeds in rounds. In each round: * Alice provides a positive integer sequence $T$ of length $N$. * Bob sees the $T$ given by Alice, then chooses an integer $x$ in $[0, N-1]$. * Then we transform $S$ into $S'$ by the following rule: $${S'}_{i} = S_{i} + T_{(i+x)\bmod N}$$ * Take $S'$ as the new $S$, and this round ends. If after some round ends, every number in $S$ is a multiple of a given prime $P$, then Alice wins. Given $N$ and the initial sequence $S$, determine whether Alice can guarantee a win in finitely many steps. If yes, what is the minimum number of rounds in which she can guarantee a win.

The first line contains two non-negative integers $N, P$, and $P$ is guaranteed to be a prime. The next line contains $N$ integers separated by spaces, describing the initial sequence $S$ ($0\le S_i \le 10^9$). It is guaranteed that $N\le 3\times 10^5$ and $P\le 200$.

Output one integer. If Alice cannot guarantee a win in finitely many steps, output $-1$. Otherwise, output an integer $x$ indicating the minimum number of rounds in which Alice can win.

### Sample Explanation One possible game process is: * Round 1: $T=[1, 0, 1, 0]$, $x=0$, and the transformed sequence is $S'=[1,1,1,1]$. * Round 2: $T=[1,1,1,1]$. No matter what $x$ is, the transformed sequence is $S'=[2,2,2,2]$. It can be proved that $2$ rounds is optimal. ##### Copyright Information From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2019. Resources such as solutions can be found at . Translated by ChatGPT 5