In general, a ranking scheme can be thought of as a vector of positive weights. This vector is multiplied with the vector of medals won by each country, and the scalar product of the two vectors defines the score of the respective country, which is then used to produce the ranking. In this general scheme, the European ranking technique corresponds to the weight vector $(10^{20}, 10^{10}, 1)$, whereas the Canadian method corresponds to the vector $(1, 1, 1)$.
In this problem, you will only need to consider weight vectors of the form $(1/n^ j, 1/n^ k, 1/n^ l)$, where $n$ is the total number of medals won by all athletes in the Olympic Games, and $j$, $k$, and $l$ are integers.
Given a list of countries and the number of gold, silver, and bronze medals won by each country, print the line
Canada wins!
if there is a weight vector of the above form such that Canada ranks first (possibly tied with one or more other countries) according to the ranking scheme defined by that vector. Print the line
Canada cannot win.
if no such vector exists.
The input contains multiple test cases. Each test case starts with an integer $c$, the number of countries to follow. Each of the following $c$ lines contains the name of a country and three integers $g$, $s$, and $b$ – the number of gold, silver, and bronze medals won by the country. The last test case has $c = 0$ and must not be processed. It is guaranteed that each test case contains at most $20$ different countries and that the total number of medals smaller than $100$. Country names do not contain whitespace characters.
Sample Input 1 | Sample Output 1 |
---|---|
2 Canada 3 2 1 USA 1 2 3 2 USA 2 2 2 Canada 1 1 1 0 |
Canada wins! Canada cannot win. |