사탕 돌리기

원기둥 형태의 뚜껑이 없는 깡통 $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$)번째 줄에는 1 이상 $N$ 이하인 $K$개의 정수가 공백 하나씩을 사이로 두고 주어지며, 이는 초기 상태에서 $i$번 깡통에 들어 있는 $K$개의 사탕의 색깔들을 의미한다.

입력으로 주어진 초기 상태에서 사탕 돌리기를 정확히 $Q$번 반복 수행하여 올바른 상태로 만들 수 있다면 숫자 1을, 아니면 숫자 0을 출력한다.