$N$ 个没有盖子的圆柱形罐子排成一个圆圈。罐子按顺时针方向依次编号为 $1$ 到 $N$，每个罐子里装有 $K$ 颗糖果。因此，一共有 $N \times K$ 颗糖果。

每颗糖果都有一种用 $1$ 到 $N$ 之间的自然数表示的颜色。对于每种颜色 $c$ ($1 \le c \le N$)，在罐子中的全部 $N \times K$ 颗糖果中，颜色为 $c$ 的糖果恰好有 $K$ 颗。每个罐子中糖果的颜色由输入给出。

这里所说的“转糖果”操作是指按以下顺序依次执行这 $N$ 次移动单颗糖果的操作：

• 从 $1$ 号罐子中任意取出一颗糖果放入 $2$ 号罐子。
• 从 $2$ 号罐子中任意取出一颗糖果放入 $3$ 号罐子。
• 从 $3$ 号罐子中任意取出一颗糖果放入 $4$ 号罐子。
• ……
• 从 ($N - 1$) 号罐子中任意取出一颗糖果放入 $N$ 号罐子。
• 从 $N$ 号罐子中任意取出一颗糖果放入 $1$ 号罐子。

你将从给定的初始状态开始，恰好重复执行 $Q$ 次转糖果操作。执行完毕后，你希望颜色为 $c$ 的所有糖果都恰好位于 $c$ 号罐子中。也就是说，$1$ 号罐子中只有颜色为 $1$ 的糖果，$2$ 号罐子中只有颜色为 $2$ 的糖果，……，最后 $N$ 号罐子中只有颜色为 $N$ 的糖果。我们将这种状态称为“正确状态”。

给定每个罐子中糖果的初始情况，请编写一个程序，判断在初始状态下恰好重复执行 $Q$ 次转糖果操作后，是否能够达到上述正确状态。

数据范围

• $2 \le N \le 2\;000$
• $1 \le K \le 2\;000$
• $1 \le Q \le 1\;000\;000\;000$
• 对于所有颜色 $c$ ($1 \le c \le N$)，颜色为 $c$ 的糖果恰好有 $K$ 颗。

子任务

1. (3 分) $Q = 1$。
2. (6 分) $N = 2$。
3. (28 分) $K = 1$。
4. (40 分) $N, K \le 100$。
5. (23 分) 无附加限制。

输入格式

第一行包含三个用单个空格隔开的整数 $N, K, Q$。

接下来的 $N$ 行，第 $i$ ($1 \le i \le N$) 行包含 $K$ 个用单个空格隔开的介于 $1$ 到 $N$ 之间的整数，表示初始状态下 $i$ 号罐子中所含的 $K$ 颗糖果的颜色。

输出格式

如果从输入的初始状态开始，恰好重复执行 $Q$ 次转糖果操作能够达到正确状态，则输出数字 1，否则输出数字 0。

样例

输入格式 1

3 1 1
2
3
1

输出格式 1

1

样例

输入格式 2

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

输出格式 2

0