题目名称

魔法符文

题目描述

在神秘魔法世界中，魔法师使用由 true、false、and、or 组成的古老符文进行法术仪式，需将符文序列转化为最终魔法能量值（true 或 false ）。规则如下：

1. true 和 false 是基础魔法能量值。
2. and 和 or 是魔法连接符，用于将两个魔法能量值组合成新能量值。
3. and 符文优先级高于 or，组合符文时先计算 and 连接的能量值，再计算 or 连接的能量值。

魔法师需设计算法解析符文序列并计算最终魔法能量值。

输入格式

• 第一行：输入两个数 $n$ 和 $q$，分别表示魔法词汇个数和询问次数。
• 第二行：包含 $n$ 个字符的字符串，魔法能量值和魔法连接符交替输入，且第一个和最后一个一定是魔法能量值。
• 以下 $q$ 行：每行包含两个整数 $l$ 和 $r$ 。
  • 若 $l \leq r$ ，计算并返回区间 $[l, r]$ 范围的运算结果。
  • 若 $l > r$ ，分别计算区间 $[l, n + 2 - r]$ 和 $[r, l + 2 - n]$ 的结果 $A$、$B$、$C$ ，输出 $A$ op1 $B$ op2 $C$ 的结果，op1 和 op2 分别为第 $r - 1$ 个字符串和第 $l + 1$ 个字符串（若区间不存在则忽略该区间计算），保证 op1 和 op2 都为魔法连接符。

输出格式

共输出 $q$ 行，每行输出一个询问的结果，若计算结果为 true 则输出 T，否则输出 F 。

输入输出样例

• 输入样例

13 4
false or true and false and false and true or true and false
1 5
3 11
11 3
13 1

• 输出样例

F
T
F
F

• 样例解释
  • 第一次询问：先计算 true and false 得 false，再进行 or 运算，最终结果为 false，输出 F 。
  • 第二次询问：出现了 or，且 or 右边结果为 true，最终结果为 true，输出 T 。
  • 第三次询问：因 $l < r$ ，先算 $A=[1,2]$ 结果为 false，$B=[3,13]$ 结果为 true，$C=[12 + 2 - 13,13 + 2 - 13]=[1,2]$ 结果为 false，op1=or，op2=and，计算 $A$ or $B$ and $C$ 结果为 false，输出 F 。
  • 第四次询问：$[1,2]$ 区间不存在，$[12,13]$ 区间不存在，只有 $B=[5,8]$ ，计算 $B$ 情况，结果为 false，输出 F 。

数据范围

• $1 \leq n, q \leq 2002$，且 $n$ 为奇数 。
• 每次询问保证 $l$，$r$ 一定为奇数 。
• 20%的数据保证：输入的魔法连接符只出现 and 或者 or 其中一种。