Putata 和 Budada 正在玩一个新游戏。起初，Putata 手里有一张写着由小写字母组成的字符串的纸条。在每一轮中，持有纸条的玩家必须从纸条的开头或结尾撕掉一个字符，然后将其传给另一名玩家。如果在任何时刻，纸条上的字符串是一个回文串，那么持有该纸条的玩家输掉游戏。注意，无论是在玩家撕掉字符之前还是之后，该玩家都被视为持有纸条。一个长度为 $n$ 的字符串 $s_1s_2 \dots s_n$ 被称为回文串，当且仅当对于所有 $1 \le i \le n$，都有 $s_i = s_{n-i+1}$。

然而，当 Putata 发现这张纸条时，他发现之前已经有人玩过这张纸条了。由于 Putata 和 Budada 都非常聪明，并且总是会选择最优策略来让自己获胜，他们想知道谁会赢得游戏，并向你寻求帮助。形式化地，给定一个长度为 $n$ 的字符串，你需要回答 $q$ 个询问，每个询问由两个整数 $l$ 和 $r$ 描述，你需要确定如果 Putata 和 Budada 在字符串 $s_l s_{l+1} \dots s_r$ 上进行上述游戏，谁会获胜。

输入格式

第一行包含两个整数 $n, q$ ($1 \le n, q \le 1\,000\,000$)，分别表示字符串的长度和询问次数。 第二行包含一个长度为 $n$ 的字符串 $s$，由小写英文字母组成。 接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$ ($1 \le l \le r \le n$)，描述一个询问。

输出格式

对于每个询问，输出一行。如果 Putata 在该询问中获胜，输出 “Putata”（不含引号）。否则输出 “Budada”。

样例

输入 1

7 3
potatop
1 3
3 5
1 6

输出 1

Putata
Budada
Budada