Dla zbioru $S$ możemy posortować wszystkie jego elementy od najmniejszego do największego. Wartość różnicy zbioru definiujemy jako maksymalną różnicę między dwiema sąsiednimi liczbami w tak posortowanym ciągu.

Masz $Q$ zbiorów nieujemnych liczb całkowitych, z których każdy ma wartość różnicy nieprzekraczającą $K$. Wiadomo, że w każdym zbiorze najmniejszym elementem jest $0$, a największym $N+1$.

Dane są wyniki operacji modulo $M$ dla liczby wystąpień każdego elementu od $1$ do $N$ we wszystkich $Q$ zbiorach. Wyznacz minimalną wartość $Q$, która spełnia te warunki. Jeśli rozwiązanie nie istnieje, wypisz -1.

Wejście

W pierwszej linii znajdują się trzy liczby całkowite $N$, $K$, $M$. W kolejnej linii znajduje się $N$ liczb całkowitych, gdzie $i$-ta liczba oznacza wynik operacji modulo $M$ dla liczby wystąpień $i$-tego elementu.

Wyjście

Wypisz jedną liczbę całkowitą oznaczającą minimalną wartość $Q$. Jeśli rozwiązanie nie istnieje, wypisz -1.

Przykład 1

Wejście 1

3 2 8
0 0 1

Wyjście 1

8

Przykład 2

Wejście 2

3 1 9
2 3 3

Wyjście 2

-1

Ograniczenia

Dla 10% danych: $K = 1$.

Dla kolejnych 10% danych: $K = 2$ oraz $N = 5$.

Dla kolejnych 20% danych: $K = 2$ oraz $N \leq 50$.

Dla kolejnych 15% danych: gwarantowane, że odpowiedź jest mniejsza niż $M$ oraz $N \leq 50$.

Dla kolejnych 25% danych: $N \leq 20$.

Dla 100% danych: $1 \leq N \leq 500000, 1 \leq K \leq N, 2 \leq M \leq 10^9$.