円筒形の蓋のない缶が $N$ 個、円形に並べられている。各缶には時計回りの順に 1 番から $N$ 番までの自然数番号が付けられており、各缶には飴が $K$ 個ずつ入っている。したがって、飴は全部で $N \times K$ 個ある。

すべての飴は 1 以上 $N$ 以下の自然数で表される色を持っている。すべての色 $c$ ($1 \le c \le N$) について、缶に入っている合計 $N \times K$ 個の飴のうち、色が $c$ である飴はちょうど $K$ 個ある。各缶に入っている飴の色は入力として与えられる。

ここで、「飴回し」という操作は、以下のように飴を 1 個ずつ移動させる $N$ 回の作業を、以下に示す順序で行うことをいう。

• 1 番の缶から飴を任意に 1 個取り出し、2 番の缶に入れる。
• 2 番の缶から飴を任意に 1 個取り出し、3 番の缶に入れる。
• 3 番の缶から飴を任意に 1 個取り出し、4 番の缶に入れる。
• .......
• ($N - 1$) 番の缶から飴を任意に 1 個取り出し、$N$ 番の缶に入れる。
• $N$ 番の缶から飴を任意に 1 個取り出し、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点) 追加の制約はない。

入力

1 行目に $N, K, Q$ が空白区切りで与えられる。

続く $N$ 行のうち $i$ 行目 ($1 \le i \le N$) には、1 以上 $N$ 以下の $K$ 個の整数が空白区切りで与えられ、これは初期状態で $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