读写要求

本题采用文件读写，请在提交代码时使用正确的文件名，否则会导致 RE。

输入文件：barbecue.in

输出文件：barbecue.out

题目描述

Putata 和 Budada 在玩一个字符串博弈。

初始有一个字符串，当前持有字符串的玩家每回合必须从左端或右端删除恰好一个字符，然后把字符串交给对手。

若在任意时刻（包括删前和删后）当前字符串是回文串，则当前持有字符串的玩家立刻失败。

现在给定长度为 $n$ 的原串 $s$，你需要回答 $q$ 次询问。每次询问给出区间 $[l,r]$，表示只在子串 $s_ls_{l+1}\dots s_r$ 上进行上述游戏，且 Putata 先手。

双方都采取最优策略，判断先手是否能获胜。

输入格式

第一行两个整数 $n,q$，分别表示字符串长度与询问个数。

第二行一个长度为 $n$ 的仅含小写字母的字符串 $s$。

接下来 $q$ 行，每行两个整数 $l,r$，表示一次询问。

输出格式

对每个询问输出一行：

• 若 Putata 必胜，输出 Putata；
• 否则输出 Budada。

数据范围

$1\le n,q\le 10^6$，$1\le l\le r\le n$。

输入输出样例

7 3
potatop
1 3
3 5
1 6

Putata
Budada
Budada

说明

回文串定义为：设串长为 $m$，若对所有 $1\le i\le m$ 都有 $s_i=s_{m-i+1}$，则该串为回文串。