#717. 【北大集训2021】扑克比大小

• 在游戏开始前，系统会给小 $Z$ 和小 $A$ 各发一堆手牌（两堆牌数量可能不相同），其中每张牌上写有一个小写字母。

• 在游戏的每一轮，小 $Z$ 和小 $A$ 同时翻开牌堆顶的第一张牌，若两人翻开的牌不同，则牌上对应小写字母更小的那一方获胜；若两人翻开的牌相同，则他们会将翻开的牌塞入牌堆底，继续游戏，直到某方获胜为止。

样例

input

abbab
5 0
1 3
2 4
3 5
1 4
2 5



output

4
7
6
2
8



数据范围与提示

$1$ $3$ $10^{2}$ $10^{2}$ $0$
$2$ $3$ $500$ $2000$
$3$ $4$ $2000$
$4$ $5$ $2 \times 10^{4}$
$5$ $13$ $10^{5}$ $10^{5}$ $3$
$6$ $17$ $0$
$7$ $15$ $5 \times 10^{5}$ $5 \times 10^{5}$ $1$
$8$ $15$ $2$
$9$ $25$ $0$

• $type=0$，数据无特殊限制。

• $type=1$，保证 $\exists 1\le l'\le r'\le |a|$，$a_{l_i,r_i}+a_{l_i,r_i}=a_{l',r'}$。

• $type=2$，保证 $\forall r'-l'=r_i-l_i+1$，若 $a_{l',r'-1}=a_{l_i,r_i}$，则必有 $a_{r'}\neq a_{l_i}$。

• $type=3$，保证 $\sum r_i-l_i \le 10^5$。

hack

hack 数据必须保证 $type=0$。