궁전 게임

시간 제한0.5초메모리 제한512 MB

요약
3000x3000 체스판에 놓인 N개의 palace를 번갈아 하나씩 왼쪽 아래로(맨해튼 거리를 줄이며) 룩 또는 킹처럼 이동시키고, 더 이상 움직일 수 없는 쪽이 지는 게임에서 승자를 판정한다.
난이도

보통10점 중 7점

유형
게임 이론, 수학, 구현
정답자
아직 제출이 없습니다

문제

궁전은 구사과가 16878번에서 새로 만든 체스 말이다. 궁전은 룩의 이동 방법과 킹의 이동 방법을 모두 사용할 수 있다. 즉, 같은 행이나 열에 있는 칸, 또는 인접한 네 방향과 대각선 네 방향으로 이동할 수 있다.

오늘은 큐브러버와 함께 궁전을 이용한 게임을 하려고 한다.

크기가 3000×3000인 체스판 위에 궁전 N개가 놓여 있다. 구사과와 큐브러버는 턴을 번갈아가면서 게임을 하며, 각 턴은 다음과 같이 이루어진다.

  • 체스판 위에 있는 궁전을 하나 고르고, 왼쪽 아랫 방향으로 한 번 옮긴다. 즉, 가장 왼쪽 아랫칸과 "맨해튼 거리"가 감소해야 한다.

더 이상 궁전을 이동시킬 수 없는 플레이어가 게임을 지게 된다.

두 사람이 최적의 방법으로 게임을 진행했을 때, 누가 이기는지 구하는 프로그램을 작성하시오. 게임은 구사과가 먼저 시작하며, 두 개 이상의 궁전이 하나의 칸에 동시에 있을 수 있다.

가장 왼쪽 아랫칸의 좌표는 (0, 0)이고, 오른쪽 윗칸의 좌표는 (2999, 2999)이다.

입력

첫째 줄에 궁전의 개수 N(1 ≤ N ≤ 300,000)이 주어진다. 둘째 줄부터 N개의 줄에 궁전의 좌표 x, y (0 ≤ x, y < 3000)가 한 줄에 하나씩 주어진다.

출력

구사과가 게임을 이기는 경우에는 "koosaga"를, 큐브러버가 이기는 경우에는 "cubelover"를 출력한다.

예제5

  1. 예제 1

    입력
    1
    3 2
    
    예상 출력
    koosaga
    
  2. 예제 2

    입력
    1
    3 3
    
    예상 출력
    cubelover
    
  3. 예제 3

    입력
    1
    6 6
    
    예상 출력
    cubelover
    
  4. 예제 4

    입력
    3
    7 4
    3 7
    1 0
    
    예상 출력
    cubelover
    
  5. 예제 5

    입력
    5
    4 2
    6 9
    7 8
    2 1
    5 5
    
    예상 출력
    koosaga