MOG
Spanish
|
English

Matcom Online Grader

MOG Round #35

Ended

B - Brian plays with Fito

Languages: C, C++, Java, Python, Kotlin, C#
Time & Memory limits: (details)

Brian and Fito are playing a game with candies. Initially, there are $N$ heaps where the $i$-th of them has $a_i$ candies. In his turn, a player can only take a positive number of candies from one of the heaps. Brian plays first and they alternate moves.



If the $\text{XOR}$ sum, $a_1\, \text{XOR}\, a_2\, \text{XOR}\, ... \text{XOR}\, a_N$, of the numbers of remaining candies of these heaps, becomes $0$ as a result of a player's move, the player loses.

Given the initial configuration of the heaps, your task is to write a program that determines who will win the game. This can help Fito to decide an initial configuration that allows him to win.

Input

The input consists of a single test case. The first line contains an integer $N$ ($1 \leq N \leq 10^5$) which is the number of heaps. Each of the following $N$ lines contains an integer $a_i$ ($1 \leq a_i \leq 10^9$) that represents the number of candies in the $i$-th heap.

Output

Print one line with "Brian" if he wins (assuming he plays optimally), or "Fito" if he has a chance to win (no matter how Brian plays).

Sample test(s)

Input
1 1
Output
Fito
Input
2 1 1
Output
Brian
Input
3 1 2 3
Output
Brian