Rook, Bishop, King, Knight, and Palace Game

Time limit0.5sMemory limit512 MB

Summary

Two players take turns moving chess pieces toward the lower left on a huge board, and the task is to find who wins with optimal play.

Level: Hard9 of 10
Topics: Game theory, Math, Implementation
Solved: No attempts yet

Problem

Today, Cubelover and I are playing a game with rooks, bishops, kings, knights, and palaces.

N chess pieces are placed on a chessboard of size $(10^9-1)\times(10^9-1)$ . The pieces used in this game are rooks, bishops, kings, knights, and palaces. The palace is a chess piece that Koosaga created in problem 16878. A palace can move both like a rook and like a king. In other words, it can move to any square in the same row or column, or to one of the four adjacent squares or four diagonal squares.

Koosaga and Cubelover take turns, and each turn goes as follows.

Choose one piece on the board and move it once toward the lower left. That is, the move must decrease the Manhattan distance, and neither coordinate may increase.

A player who cannot move any piece loses.

When both players play optimally, determine who wins. Koosaga moves first. Two or more pieces may occupy the same square.

The lower left square has coordinates (0, 0), and the upper right square has coordinates ( $10^9-1$ , $10^9-1$ ).

Input

The first line contains the number of pieces $N$ ( $1 \le N \le 300,000$ ). Each of the next $N$ lines contains the coordinates $x$ , $y$ ( $0 \le x, y < 10^9$ ) and the type $c$ of one piece.

$c$ is one of R, B, K, N, or P, which mean rook, bishop, king, knight, and palace, respectively.

Output

Print "koosaga" if Koosaga wins, and "cubelover" if Cubelover wins.

Examples5

Example 1
Input
```
2
7 0 B
3 4 R
```
Expected output
```
koosaga
```
Example 2
Input
```
2
6 7 K
9 1 B
```
Expected output
```
cubelover
```
Example 3
Input
```
3
8 7 B
9 4 K
4 4 R
```
Expected output
```
koosaga
```
Example 4
Input
```
2
8 5 R
6 5 K
```
Expected output
```
koosaga
```
Example 5
Input
```
3
1 2 P
6 1 B
4 4 P
```
Expected output
```
koosaga
```