Balloon Popping

Interview

Time limit0.5sMemory limit1024 MB

Summary

Given N balloons popped by A, B, and C at multiples of x, y, and z (ties go to A, then B, then C), print who pops the last balloon.

Level: Medium4 of 10
Topics: Math, Binary search
Solved: No attempts yet

Problem

A, B, and C play a game where they pop $N$ balloons.

A pops one balloon every $x$ minutes. A pops balloons at minutes $x, 2x, 3x, \ldots$ after the game starts.
B pops one balloon every $y$ minutes. B pops balloons at minutes $y, 2y, 3y, \ldots$ after the game starts.
C pops one balloon every $z$ minutes. C pops balloons at minutes $z, 2z, 3z, \ldots$ after the game starts.
If two or more people pop a balloon at the same time, they pop in the order A, B, C.

The person who pops the last balloon wins. Print the winner among A, B, and C.

Input

The first line contains the number of balloons $N$ and the times $x$ , $y$ , $z$ it takes to pop a balloon. ( $1 \le N, x, y, z \le 10^9$ , and $N$ , $x$ , $y$ , $z$ are all integers.)

Output

Print the winner of the game. Print A win if A wins, B win if B wins, or C win if C wins.

Examples1

Example 1
Input
```
10 5 3 6
```
Expected output
```
B win
```