Putata and Budada are playing a new game. In the beginning, there are $n$ piles of stones. Two players take turns to play the game, and Putata goes first. In each round, if it is Putata's turn, then he can choose a pile and remove any positive number of stones from it. If it is Budada's turn, then he can choose a pile and remove exactly one stone from it. When a pile becomes empty, it will disappear and cannot be chosen in the remaining rounds. The player who takes away the last stone wins the game.

Since both Putata and Budada are clever and will always choose the best way to make themselves win, they wonder who will win the game, and they ask you for help. Please find the winner when both players play optimally.

Input

The first line contains an integer $n$ ($1 \leq n \leq 10^5$), denoting the number of piles.

The second line contains $n$ positive integers $a_i$ ($1 \leq a_i \leq 10^9$), denoting the number of stones in each pile.

Output

Print a single line. If Putata wins the game, output Putata. Otherwise output Budada.

Examples

Input 1

6
1 1 4 5 1 4

Output 1

Putata

Input 2

2
1 1

Output 2

Budada