圓柱形且沒有蓋子的罐子 $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