소수 제곱 게임

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

요약

두 사람이 번갈아 소수의 거듭제곱 p^k를 골라, 그 값으로 나누어떨어지는 모든 원소를 나눕니다. 더 이상 고를 수 없는 사람이 지며, 선공이 이기는지 구합니다.

난이도: 어려움10점 중 8점
유형: 수학, 정수론, 게임 이론, 비트 연산
정답자: 아직 제출이 없습니다

문제

구사과와 큐브러버는 소수 제곱 게임을 하려고 한다. 이 게임은 길이가 $N$ 인 수열 $A_1, A_2, \ldots, A_N$ 을 사용한다. 두 사람은 턴을 번갈아 가지면서 게임을 진행한다.

각 턴에서 플레이어는 정수 $p$ 와 $k$ 를 고른다. 이때 $p$ 는 소수이고 $k$ 는 양의 정수여야 한다. 또한 $p^k$ 는 수열에 있는 정수 중 적어도 하나를 나눌 수 있어야 한다. 그다음 수열에서 $p^k$ 로 나누어 떨어지는 모든 수를 $p^k$ 로 나눈다. $p$ 와 $k$ 를 고를 수 없는 사람이 게임에서 진다.

두 사람이 최적의 방법으로 게임을 진행했을 때 누가 이기는지 구하는 프로그램을 작성하시오. 게임은 구사과가 먼저 턴을 갖는다.

입력

첫째 줄에 수열의 크기 $N$ ( $1 \le N \le 100$ )이 주어진다. 둘째 줄에는 $A_1, A_2, \ldots, A_N$ ( $1 \le A_i \le 10^9$ )이 주어진다.

출력

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

예제4

예제 1
입력
```
4
1 1 1 1
```
예상 출력
```
cubelover
```
예제 2
입력
```
4
1 1 17 17
```
예상 출력
```
koosaga
```
예제 3
입력
```
4
1 1 17 289
```
예상 출력
```
cubelover
```
예제 4
입력
```
5
1 2 3 4 5
```
예상 출력
```
cubelover
```