There are $N$ cylindrical, lidless cans arranged in a circle. The cans are numbered from $1$ to $N$ in clockwise order, and each can contains $K$ candies. Therefore, there are $N \times K$ candies in total.

Each candy has a color represented by a natural number between $1$ and $N$, inclusive. For every color $c$ ($1 \le c \le N$), among all $N \times K$ candies in the cans, there are exactly $K$ candies of color $c$. The colors of the candies in each can are given as input.

An operation called candy rotation consists of performing the following $N$ candy-moving steps in the order given below:

• Choose an arbitrary candy from can $1$ and move it to can $2$.
• Choose an arbitrary candy from can $2$ and move it to can $3$.
• Choose an arbitrary candy from can $3$ and move it to can $4$.
• .......
• Choose an arbitrary candy from can $(N - 1)$ and move it to can $N$.
• Choose an arbitrary candy from can $N$ and move it to can $1$.

You will perform candy rotations exactly $Q$ times starting from the given initial state. After the operations, you want all candies of color $c$ to be in can $c$. That is, can $1$ contains only candies of color $1$, can $2$ contains only candies of color $2$, ..., and finally can $N$ contains only candies of color $N$. Let us call this a correct state.

Given the state of candies in each can as input, write a program to determine whether it is possible to reach the correct state described above after performing candy rotations exactly $Q$ times from the initial state.

Constraints

• $2 \le N \le 2\ 000$
• $1 \le K \le 2\ 000$
• $1 \le Q \le 1\ 000\ 000\ 000$
• For every color $c$ ($1 \le c \le N$), there are exactly $K$ candies of color $c$.

Subtasks

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) No additional constraints.

Input

The first line contains $N$, $K$, and $Q$ separated by a space.

Each of the following $N$ lines contains $K$ integers between $1$ and $N$, inclusive, separated by spaces. The $i$-th line ($1 \le i \le N$) represents the colors of the $K$ candies initially in can $i$.

Output

Print 1 if it is possible to reach the correct state by performing candy rotations exactly $Q$ times from the given initial state, or 0 otherwise.

Examples

Input 1

3 1 1
2
3
1

Output 1

1

Examples

Input 2

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

Output 2

0