问题
我们更喜欢正确的括号序列。正确的括号序列定义如下。
- 空字符串是正确的括号序列。
-
如果字符串 s 是正确的括号序列,
(+s+)也是正确的括号序列。 - 如果字符串 s 和 t 是正确的括号序列, s + t 也是正确的括号序列。
你有一个字符串 S 长度 N.
S 仅包含
(, ),和 ?.
你的任务是回答 Q 关于字符串的问题 S。 的 i第一个问题如下:
-
让 S_i 是以下子串 S 来自 l_i- 第一个字符 r_i- 第一个字符,包含在内。是否有可能使 S_i 通过替换每个出现的正确的括号序列
?与(or)?
输入
输入由标准输入按以下格式给出。
N S Q l_1 r_1 l_2 r_2 : l_Q r_Q
- 第一行,整数 写入 N (1≦N≦10^5),表示字符串的长度 S.
-
第二行,字符串
写入 S 。 S 仅包含
(,),和?. - 第三行,整数 Q (1≦Q≦10^5)被写入, 这表明问题的数量。
- 后续 Q 行描述了问题。 i其中第行包含两个整数 l_i 和 r_i (1≦l_i≦r_i≦N),用空格分隔。
输出
输出 Q 行。 i第行,打印 Yes or No,根据答案 i- 第一个问题。
输入示例 1
4 ?()? 6 1 2 2 3 3 4 1 3 2 4 1 4
输出示例 1
No Yes No No No Yes
输入示例 2
10 (?)?)?(?)) 10 2 2 6 9 6 7 3 5 4 8 2 9 1 2 6 8 2 4 1 4
输出示例 2
No Yes No No No Yes Yes No No Yes