룩, 비숍, 킹, 나이트, 궁전 게임

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

요약

두 사람이 체스 말을 번갈아 왼쪽 아래로 옮기는 게임에서, 최적으로 둘 때 누가 이기는지 구합니다.

난이도: 어려움10점 중 9점
유형: 게임 이론, 수학, 구현
정답자: 아직 제출이 없습니다

문제

오늘은 큐브러버와 함께 룩, 비숍, 킹, 나이트, 궁전을 이용한 게임을 하려고 한다.

크기가 $(10^9-1)\times(10^9-1)$ 인 체스판 위에 체스말 $N$ 개가 놓여 있다. 이 게임에서 사용하는 체스말은 룩, 비숍, 킹, 나이트, 궁전이다. 궁전은 구사과가 16878번에서 새로 만든 체스 말이다. 궁전은 룩의 이동 방법과 킹의 이동 방법을 모두 사용할 수 있다. 즉, 같은 행 또는 열에 있는 칸이나 인접한 네 방향과 대각선 네 방향으로 이동할 수 있다.

구사과와 큐브러버는 턴을 번갈아 가며 게임을 하고, 각 턴은 다음과 같이 진행된다.

체스판 위에 있는 체스말을 하나 고르고, 왼쪽 아랫 방향으로 한 번 옮긴다. 즉, "맨해튼 거리"가 감소해야 하며, 두 좌표가 모두 증가하지 않아야 한다.

더 이상 체스말을 이동시킬 수 없는 플레이어가 게임에서 진다.

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

가장 왼쪽 아랫칸의 좌표는 (0, 0)이고, 오른쪽 윗칸의 좌표는 ( $10^9-1$ , $10^9-1$ )이다.

입력

첫째 줄에 체스말의 개수 $N$ ( $1 \le N \le 300,000$ )이 주어진다. 둘째 줄부터 $N$ 개의 줄에 체스말의 좌표 $x$ , $y$ ( $0 \le x, y < 10^9$ )와 체스말의 종류 $c$ 가 한 줄에 하나씩 주어진다.

$c$ 는 R, B, K, N, P 중 하나이며, 순서대로 룩, 비숍, 킹, 나이트, 궁전을 뜻한다.

출력

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

예제5

예제 1
입력
```
2
7 0 B
3 4 R
```
예상 출력
```
koosaga
```
예제 2
입력
```
2
6 7 K
9 1 B
```
예상 출력
```
cubelover
```
예제 3
입력
```
3
8 7 B
9 4 K
4 4 R
```
예상 출력
```
koosaga
```
예제 4
입력
```
2
8 5 R
6 5 K
```
예상 출력
```
koosaga
```
예제 5
입력
```
3
1 2 P
6 1 B
4 4 P
```
예상 출력
```
koosaga
```