Có $N$ chiếc hộp hình trụ không có nắp được xếp thành một vòng tròn. Các hộp được đánh số bằng các số tự nhiên từ 1 đến $N$ theo chiều kim đồng hồ, và mỗi hộp chứa $K$ viên kẹo. Do đó, có tổng cộng $N \times K$ viên kẹo.

Mỗi viên kẹo có một màu được biểu diễn bằng một số tự nhiên từ 1 đến $N$. Với mỗi màu $c$ ($1 \le c \le N$), trong tổng số $N \times K$ viên kẹo ở các hộp, có đúng $K$ viên kẹo có màu $c$. Màu của các viên kẹo trong mỗi hộp được cho trong dữ liệu vào.

Thao tác xoay kẹo là việc thực hiện $N$ bước chuyển kẹo lần lượt từng viên một theo thứ tự dưới đây:

• Chọn tùy ý một viên kẹo từ hộp 1 rồi bỏ vào hộp 2.
• Chọn tùy ý một viên kẹo từ hộp 2 rồi bỏ vào hộp 3.
• Chọn tùy ý một viên kẹo từ hộp 3 rồi bỏ vào hộp 4.
• .......
• Chọn tùy ý một viên kẹo từ hộp ($N - 1$) rồi bỏ vào hộp $N$.
• Chọn tùy ý một viên kẹo từ hộp $N$ rồi bỏ vào hộp 1.

Từ trạng thái ban đầu đã cho, bạn sẽ thực hiện lặp lại thao tác xoay kẹo đúng $Q$ lần. Sau khi thực hiện xong, bạn muốn tất cả các viên kẹo có màu $c$ đều nằm trong hộp $c$. Tức là trong hộp 1 chỉ có kẹo mang màu 1, trong hộp 2 chỉ có kẹo mang màu 2, ..., cuối cùng trong hộp $N$ chỉ có kẹo mang màu $N$. Ta gọi trạng thái này là trạng thái hợp lệ.

Cho trạng thái kẹo trong mỗi hộp ở dữ liệu vào, hãy viết chương trình xác định xem từ trạng thái ban đầu, sau khi thực hiện thao tác xoay kẹo đúng $Q$ lần, có thể đạt được trạng thái hợp lệ như mô tả ở trên hay không.

Giới hạn

• $2 \le N \le 2\ 000$
• $1 \le K \le 2\ 000$
• $1 \le Q \le 1\ 000\ 000\ 000$
• Với mỗi màu $c$ ($1 \le c \le N$), có đúng $K$ viên kẹo có màu $c$.

Subtask

1. (3 điểm) $Q = 1$.
2. (6 điểm) $N = 2$.
3. (28 điểm) $K = 1$.
4. (40 điểm) $N, K \le 100$.
5. (23 điểm) Không có ràng buộc bổ sung nào.

Dữ liệu vào

Dòng đầu tiên chứa ba số $N, K, Q$ cách nhau bởi một dấu cách.

Trong $N$ dòng tiếp theo, dòng thứ $i$ ($1 \le i \le N$) chứa $K$ số nguyên từ 1 đến $N$, phân tách nhau bởi một dấu cách, biểu thị màu sắc của $K$ viên kẹo trong hộp thứ $i$ ở trạng thái ban đầu.

Dữ liệu ra

Nếu từ trạng thái ban đầu cho trước, sau khi lặp lại thao tác xoay kẹo đúng $Q$ lần có thể đạt được trạng thái hợp lệ thì in ra số 1, ngược lại in ra số 0.

Ví dụ

Dữ liệu vào 1

3 1 1
2
3
1

Dữ liệu ra 1

1

Dữ liệu vào 2

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

Dữ liệu ra 2

0