원기둥 형태의 뚜껑이 없는 깡통 N개가 원형으로 배열되어 있다.

각 깡통에는 시계 방향 순서대로 1번부터 N번 까지의 자연 수 번호가 붙어 있으며,

각 깡통에는 사탕이 K개씩 들어 있다. 따라서, 총 N × K개의 사탕이 있는 것이다.

모든 사탕은 1 이상 N 이하의 자연수로 표현되는 색깔을 가진다.

모든 색 c (1 ≤ c ≤ N)에 대해, 깡통에 들어 있는 총 N × K개의 사탕 중 색깔이 c인 사탕은 정확히 K개 있다.

각 깡통에 들어 있는 사탕의 색이 무엇인지는 입력으로 주어진다.

이때 사탕 돌리기라는 연산은 아래와 같이 사탕을 하나씩 옮기는 N개의 작업을, 아래에 주어진 순서대로 수행하는 것을 말한다.

당신은 주어진 초기 상태에서 사탕 돌리기를 정확히 Q번 반복 수행할 것이다.

수행한 이후에 당신은 c의 색깔을 가지는 모든 사탕이 c번 깡통에 들어가도록 하고 싶다.

즉, 1번 깡통에는 1번 색깔의 사탕만이 존재하고, 2번 깡통에는 2번 색깔의 사탕만이 존재하고, ....,

마지막으로 N번 깡통에는 N번 색깔의 사탕만이 존재하도록 하고자 한다.

이러한 상태를 올바른 상태라고 하자.

입력으로 각 깡통에 들어 있는 사탕의 상황이 주어질 때,

초기 상태에서 사탕 돌리기를 정확히 Q번 반복 수행한 후 위에서 설명한 올바른 상태를 이룰 수 있는지 판단하는 프로그램을 작성하라.

사탕 돌리기 timer 1s memory 256MB

사탕 돌리기 1s 256MB