题目描述
普塔塔和布达达在玩一个新游戏。一开始，普塔塔有一个纸条，上面有一个由小写字母组成的字符串。在每一轮中，拥有纸条的玩家必须从纸条的开头或结尾撕下一个字符，然后将纸条传递给另一个玩家。如果在任何时候，纸条上的字符串是回文串，那么拥有纸条的玩家就输了。请注意，在玩家从纸条上撕下字符之前或之后，玩家都被认为拥有这个纸条。如果对于从$1$到$n$的所有整数$i$， $s_i=s_{n-i+1}$，则长度为$n$的字符串$s_1s_2\dots s_n$被认为是回文。
给你一个长度为$n$的字符串，你必须回答$q$个查询，每个查询由两个整数$l$和$r$描述，这意味着你必须确定如果普塔塔和布达达在写着字符串$s_ls_{l+1}\dots s_r$的纸条上进行上述游戏，谁将获胜。两个人都会采用尽量让自己获胜的策略。
输入格式
第一行输入两个整数$n,q$，代表字符串的长度和询问的数量。
第二行输入一个长度为$n$的字符串$s$。
接下来$q$行每行有两个整数$l, r$，代表一个询问。
输出格式
对于每个询问，输出一行一个字符串。如果普塔塔会获胜，输出Putata，否则输出Budada。
输入样例1
7 3
potatop
1 3
3 5
1 6输出样例1
Putata
Budada
Budada样例2见下载文件。
数据范围
对于$40\%$的数据，保证$ n,q\leq 10$。
对于$80\%$的数据，保证$n,m\leq 1000$。
对于所有数据，保证$n,q\leq 10^6$，保证字符串只包含小写字母。
