WINNER - Who is the winner

no tags 

Having nothing to do, Bom and Cuoi invented a game as the following: there are N heaps of stones; the ith heap contains ai stones. Bom and Cuoi alternatively takes turn to play. Who has his turn may pick any heap of stones and remove some stones from that heap. The number of removed stones must be a divisor of the number of stones in that heap.

Who removes the last stone is the winner. Bom takes his move first.

Given the initial number of stones in each heap, could you write a program to tell who is the winner in this game (if both players play optimally)?


The first line contains N, the number of heaps.

The second line contains N positive integers separated by spaces described the number of stones in the heaps.


In the first line, print either the string "Bom" or "Cuoi" depending on whether Bom or Cuoi will win the game.

In case Bom can win, print two numbers "x a" in the second line meaning that, in order to win the game, Bom needs to remove x stones from a heap that currently has a stones. In case there are more than one winning moves, find the winning move that has the largest x. If there is still ambiguity, among the winning moves that have the largest x, find the winning move that has the largest a.


  • 1 ≤ N ≤ 105, 1 ≤ ai ≤ 109
  • There is 70% of the test cases in which ai ≤ 105


1 2 3

2 2

Output details: After Bom removes completely the heap of 2 stones, there remain two heaps of 1 and 3 stones. If Cuoi removes completely one of the two heaps, Bom will remove the remaining heap and win the game. If Cuoi takes one stone from the heap of 3 stones, Bom will take one more stone from that same heap. There remain two heaps, each heap has two stones and Bom will be sure of a win.

Added by:Duc
Time limit:0.600s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:VNOI Marathon 2009
Round 3
Problem Setter: Ngô Minh Đức