409694: GYM103687 I Barbecue

Putata and Budada are playing a new game. In the beginning, Putata has a note with a string consists of lowercase letters on it. In each round, the player who has the note must rip off a character from the beginning or the end of the note, then pass it to the other player. If at any moment, the string on the note is a palindrome, then the player who has the note loses. Notice that both before or after the player ripping off a character from the note, the player is considered to have the note. A string $$$s_1s_2\dots s_n$$$ of length $$$n$$$ is considered to be a palindrome if for all integers $$$i$$$ from $$$1$$$ to $$$n$$$, $$$s_i=s_{n-i+1}$$$.

However, when Putata found the note, he found that someone have played on this note before. 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. Formally, you are given a string of length $$$n$$$ and you have to answer $$$q$$$ queries, each query is described by two integers $$$l$$$ and $$$r$$$, which means you have to determine who will win if Putata and Budada play the game described above on string $$$s_ls_{l+1}\dots s_r$$$ .

The first line contains two integers $$$n, q\ (1\leq n, q\leq 1\,000\,000)$$$, denoting the length of the string and the number of queries.

The second line contains a string $$$s$$$ of length $$$n$$$, consisting of lowercase English letters.

Each of the following $$$q$$$ lines contains two integers $$$l$$$ and $$$r\ (1\leq l\leq r\leq n)$$$, describing a query.

For each query, print a single line. If Putata wins the game in one query, output "Putata" (without quotes). Otherwise output "Budada".

7 3
potatop
1 3
3 5
1 6

Putata
Budada
Budada