Hay $N$ latas cilíndricas sin tapa dispuestas en círculo. Cada lata está numerada con un entero del 1 al $N$ en el sentido de las agujas del reloj, y cada lata contiene $K$ caramelos. Por lo tanto, hay un total de $N \times K$ caramelos.

Todos los caramelos tienen un color representado por un número natural entre 1 y $N$, inclusive. Para todo color $c$ ($1 \le c \le N$), de los $N \times K$ caramelos en total en las latas, hay exactamente $K$ caramelos de color $c$. Los colores de los caramelos contenidos en cada lata se proporcionan en la entrada.

Una operación llamada rotación de caramelos consiste en realizar las siguientes $N$ tareas de mover caramelos uno a uno, en el orden dado a continuación:

• Tomar un caramelo arbitrario de la lata 1 y ponerlo en la lata 2.
• Tomar un caramelo arbitrario de la lata 2 y ponerlo en la lata 3.
• Tomar un caramelo arbitrario de la lata 3 y ponerlo en la lata 4.
• .......
• Tomar un caramelo arbitrario de la lata $(N - 1)$ y ponerlo en la lata $N$.
• Tomar un caramelo arbitrario de la lata $N$ y ponerlo en la lata 1.

A partir del estado inicial dado, realizarás la rotación de caramelos exactamente $Q$ veces consecutivas. Después de realizarlas, deseas que todos los caramelos de color $c$ se encuentren en la lata $c$. Es decir, en la lata 1 solo deben existir caramelos de color 1, en la lata 2 solo caramelos de color 2, ..., y finalmente, en la lata $N$ solo caramelos de color $N$. A dicho estado lo llamaremos un estado correcto.

Dado el estado de los caramelos en cada lata como entrada, escribe un programa que determine si es posible alcanzar el estado correcto descrito anteriormente tras realizar la rotación de caramelos exactamente $Q$ veces consecutivas a partir del estado inicial.

Restricciones

• $2 \le N \le 2\,000$
• $1 \le K \le 2\,000$
• $1 \le Q \le 1\,000\,000\,000$
• Para todo color $c$ ($1 \le c \le N$), hay exactamente $K$ caramelos de color $c$.

Subtareas

1. (3 puntos) $Q = 1$.
2. (6 puntos) $N = 2$.
3. (28 puntos) $K = 1$.
4. (40 puntos) $N, K \le 100$.
5. (23 puntos) Sin restricciones adicionales.

Entrada

La primera línea contiene $N, K, Q$ separados por un espacio.

En las siguientes $N$ líneas, la $i$-ésima línea ($1 \le i \le N$) contiene $K$ enteros entre 1 y $N$, inclusive, separados por un espacio, que representan los colores de los $K$ caramelos contenidos en la lata $i$ en el estado inicial.

Salida

Imprime el número 1 si se puede alcanzar el estado correcto realizando la rotación de caramelos exactamente $Q$ veces a partir del estado inicial dado en la entrada, o el número 0 en caso contrario.

Ejemplos

Entrada 1

3 1 1
2
3
1

Salida 1

1

Entrada 2

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

Salida 2

0