题目描述

译自 COI $2020$ T$4$「Zagrade」

众所周知，CIA 是一个负责收集，处理和分析国家安全情报的机构。他们也被怀疑拥有一个巨大的常用计算机密码库，并且在开发一些十分复杂的计算机密码破解工具。

现在风水轮流转了，你的任务是破解一个 CIA 服务器的安全系统。祝你好运！

他们自然深知一些人们在密码中使用的典型模式串。因此像尝试 123456，password，1q2w3e4r 或者 welcome 这些密码都是无效的。幸运的是，我们有一些未被发现的信息可能对你有用。

服务器的主密码由恰好 $N$ 个字符组成，这里 $N$ 是一个偶数。恰好一半的字符是左括号（即 (），剩下恰好一半的字符是右括号（即 )）。此外，他们的工程师决定暴露一个 API 给健忘的管理员，而不是使用通常的「忘记密码」功能。调用这个 API，管理员可以执行最多 $Q$ 次询问「密码从第 $a$ 个字符到第 $b$ 个字符组成的这个括号序列是否是数学意义上合法的」。

一个括号序列在数学意义上合法被如下递归定义：

• () 是数学意义上合法的括号序列。

• 如果 $A$ 是数学意义上合法的括号序列，则 ($A$) 也是数学意义上合法的括号序列。

• 如果 $A$ 和 $B$ 是数学意义上合法的括号序列，则 $AB$ 也是数学意义上合法的括号序列。

交互样例

数据规模与约定