20189번 - 사탕 돌리기 서브태스크

원기둥 형태의 뚜껑이 없는 깡통 N개가 원형으로 배열되어 있다. 각 깡통에는 시계 방향 순서대로 1번부터 N번까지의 자연수 번호가 붙어 있으며, 각 깡통에는 사탕이 K개씩 들어 있다. 따라서, 총 N ×K개의 사탕이 있는 것이다.

모든 사탕은 1 이상 N 이하의 자연수로 표현되는 색깔을 가진다. 모든 색 c (1 ≤ c ≤ N)에 대해, 깡통에 들어 있는 총 N × 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번 반복 수행한 후 위에서 설명한 올바른 상태를 이룰 수 있는지 판단하는 프로그램을 작성하라.

첫 번째 줄에 N, K, Q가 공백 하나를 사이로 두고 주어진다.

이어지는 N개의 줄의 각 i (1 ≤ i ≤ N)번째 줄에는 1 이상 N 이하인 K개의 정수가 공백 하나씩을 사이로 두고 주어지며, 이는 초기 상태에서 i번 깡통에 들어 있는 K개의 사탕의 색깔들을 의미한다.

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

• 2 ≤ N ≤ 2 000
• 1 ≤ K ≤ 2 000
• 1 ≤ Q ≤ 1 000 000 000
• 모든 색깔 c (1 ≤ c ≤ N)에 대해, 색깔이 c인 사탕은 정확히 K개 있다.