Description

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:

• 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.

Input Format

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 Format

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.

4 2
0 1 0 1

2

Hint

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 https://github.com/wangyurzee7/THUPC2019.

Translated by ChatGPT 5