Wokół okręgu ustawiono $N$ cylindrycznych puszek bez pokrywek. Puszki są ponumerowane kolejnymi liczbami naturalnymi od 1 do $N$ zgodnie z ruchem wskazówek zegara, a w każdej puszce znajduje się $K$ cukierków. Zatem łącznie jest $N \times K$ cukierków.

Każdy cukierek ma kolor reprezentowany przez liczbę naturalną od 1 do $N$. Dla każdego koloru $c$ ($1 \le c \le N$) wśród wszystkich $N \times K$ cukierków w puszkach znajduje się dokładnie $K$ cukierków o kolorze $c$. Kolory cukierków znajdujących się w poszczególnych puszkach są podane na wejściu.

Operacja obracania cukierków polega na wykonaniu $N$ kolejnych czynności przenoszenia pojedynczego cukierka w następującej kolejności:

• Wybierz dowolny cukierek z puszki 1 i przełóż go do puszki 2.
• Wybierz dowolny cukierek z puszki 2 i przełóż go do puszki 3.
• Wybierz dowolny cukierek z puszki 3 i przełóż go do puszki 4.
• .......
• Wybierz dowolny cukierek z puszki $(N - 1)$ i przełóż go do puszki $N$.
• Wybierz dowolny cukierek z puszki $N$ i przełóż go do puszki 1.

Począwszy od podanego stanu początkowego, wykonasz operację obracania cukierków dokładnie $Q$ razy. Twoim celem jest, aby po jej wykonaniu wszystkie cukierki o kolorze $c$ znalazły się w puszce o numerze $c$. Innymi słowy, w puszce 1 powinny znajdować się wyłącznie cukierki o kolorze 1, w puszce 2 wyłącznie cukierki o kolorze 2, ..., a w puszce $N$ wyłącznie cukierki o kolorze $N$. Taki stan nazwijmy poprawnym.

Mając dany stan cukierków w puszkach na wejściu, napisz program, który rozstrzygnie, czy po wykonaniu operacji obracania cukierków dokładnie $Q$ razy ze stanu początkowego można uzyskać opisany powyżej poprawny stan.

Ograniczenia

• $2 \le N \le 2\ 000$
• $1 \le K \le 2\ 000$
• $1 \le Q \le 1\ 000\ 000\ 000$
• Dla każdego koloru $c$ ($1 \le c \le N$) istnieje dokładnie $K$ cukierków o kolorze $c$.

Podzadania

1. (3 punkty) $Q = 1$.
2. (6 punktów) $N = 2$.
3. (28 punktów) $K = 1$.
4. (40 punktów) $N, K \le 100$.
5. (23 punkty) Brak dodatkowych ograniczeń.

Wejście

W pierwszym wierszu podane są liczby $N, K, Q$ oddzielone pojedynczymi odstępami.

W kolejnych $N$ wierszach podano opisy puszek. W $i$-tym ($1 \le i \le N$) z tych wierszy znajduje się $K$ liczb całkowitych z przedziału od 1 do $N$ oddzielonych pojedynczymi odstępami, oznaczających kolory $K$ cukierków znajdujących się w $i$-tej puszce w stanie początkowym.

Wyjście

Wypisz liczbę 1, jeśli ze stanu początkowego podanego na wejściu można uzyskać poprawny stan po wykonaniu operacji obracania cukierków dokładnie $Q$ razy, albo liczbę 0 w przeciwnym razie.

Przykład

Wejście 1

3 1 1
2
3
1

Wyjście 1

1

Wejście 2

2 5 2
1 1 2 2 2
2 2 1 1 1

Wyjście 2

0