← 返回题目列表

AtCoder · mujin_pc_2016_d

D. 括号序列

中文机器翻译题面 查看原题

问题

我们更喜欢正确的括号序列。正确的括号序列定义如下。

  1. 空字符串是正确的括号序列。
  2. 如果字符串 s 是正确的括号序列, (+s+) 也是正确的括号序列。
  3. 如果字符串 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