$N$ boîtes de conserve cylindriques sans couvercle sont disposées en cercle. Chaque boîte est numérotée de 1 à $N$ dans le sens des aiguilles d'une montre, et chaque boîte contient $K$ bonbons. Il y a donc au total $N \times K$ bonbons.

Chaque bonbon possède une couleur représentée par un entier naturel compris entre 1 et $N$. Pour chaque couleur $c$ ($1 \le c \le N$), parmi les $N \times K$ bonbons au total dans les boîtes, il y a exactement $K$ bonbons de couleur $c$. La couleur des bonbons contenus dans chaque boîte est donnée en entrée.

Une opération appelée rotation de bonbons consiste à effectuer les $N$ étapes suivantes de déplacement de bonbons, un par un, dans l'ordre indiqué ci-dessous :

• Choisir arbitrairement un bonbon de la boîte 1 et le mettre dans la boîte 2.
• Choisir arbitrairement un bonbon de la boîte 2 et le mettre dans la boîte 3.
• Choisir arbitrairement un bonbon de la boîte 3 et le mettre dans la boîte 4.
• .......
• Choisir arbitrairement un bonbon de la boîte ($N - 1$) et le mettre dans la boîte $N$.
• Choisir arbitrairement un bonbon de la boîte $N$ et le mettre dans la boîte 1.

À partir de l'état initial donné, vous allez répéter l'opération de rotation de bonbons exactement $Q$ fois. Après ces opérations, vous souhaitez que tous les bonbons de couleur $c$ se trouvent dans la boîte $c$. Autrement dit, vous voulez que la boîte 1 ne contienne que des bonbons de couleur 1, la boîte 2 ne contienne que des bonbons de couleur 2, ..., et enfin la boîte $N$ ne contienne que des bonbons de couleur $N$. Appelons cet état l'état correct.

Étant donné l'état des bonbons dans chaque boîte en entrée, écrivez un programme qui détermine s'il est possible d'atteindre l'état correct décrit ci-dessus après avoir répété l'opération de rotation de bonbons exactement $Q$ fois à partir de l'état initial.

Contraintes

• $2 \le N \le 2\ 000$
• $1 \le K \le 2\ 000$
• $1 \le Q \le 1\ 000\ 000\ 000$
• Pour chaque couleur $c$ ($1 \le c \le N$), il y a exactement $K$ bonbons de couleur $c$.

Sous-tâches

1. (3 points) $Q = 1$.
2. (6 points) $N = 2$.
3. (28 points) $K = 1$.
4. (40 points) $N, K \le 100$.
5. (23 points) Aucune contrainte supplémentaire.

Entrée

La première ligne contient $N, K, Q$ séparés par un espace.

Chacune des $N$ lignes suivantes, pour la $i$-ième ligne ($1 \le i \le N$), contient $K$ entiers compris entre 1 et $N$ séparés par un espace, représentant les couleurs des $K$ bonbons contenus dans la boîte $i$ dans l'état initial.

Sortie

Affichez 1 s'il est possible d'atteindre l'état correct après avoir répété l'opération de rotation de bonbons exactement $Q$ fois à partir de l'état initial donné en entrée, et 0 sinon.

Exemples

Entrée 1

3 1 1
2
3
1

Sortie 1

1

Entrée 2

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

Sortie 2

0