Fibonacci Nim

Time limit0.5sMemory limit512 MB

Summary

Find which piles lose the Fibonacci-Nim take-away game and decide the winner of the multi-pile sum game with optimal play.

Level: Hard8 of 10
Topics: Game theory, Math, Greedy, Array
Solved: No attempts yet

Problem

koosaga and cubelover are playing "Fibonacci Nim". Fibonacci Nim is a game that adds a rule to Nim. Fibonacci Nim uses k piles of stones stacked one on top of another. Each pile has at least one stone. The two players take turns playing Fibonacci Nim. On your turn, you choose one pile and remove stones from it. The number of stones you remove must be a Fibonacci number.

The player who removes the last stone across all the piles wins the game.

koosaga moves first. Assuming both players play optimally, print the winner.

Input

The first line gives the number of piles N (1 ≤ N ≤ 10^5). The second line gives the number of stones in each pile, P_i (1 ≤ P_i ≤ 3×10^6).

Output

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

Examples5

Example 1
Input
```
6
3 3 1 8 3 4
```
Expected output
```
koosaga
```
Example 2
Input
```
1
10
```
Expected output
```
cubelover
```
Example 3
Input
```
4
3 9 5 2
```
Expected output
```
koosaga
```
Example 4
Input
```
5
10 10 6 8 10
```
Expected output
```
koosaga
```
Example 5
Input
```
1
4
```
Expected output
```
cubelover
```