D - Parenthesis Sequence Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

正しい括弧列とは、以下で定義される文字列のことです。

  1. 空文字列は正しい括弧列である。
  2. 文字列 s が正しい括弧列であるとき、(+s+) は正しい括弧列である。
  3. 文字列 s，t が正しい括弧列であるとき、s+t は正しい括弧列である。

あなたは、長さ N の文字列 S を持っています。S は (，)，? のみからなります。

S について Q 個の質問に答えてください。i 番目の質問は次のようなものです。

  • S の l_i 文字目から r_i 文字目までの連続した部分文字列を S_i とする。S_i に含まれるすべての ? をそれぞれ ( または ) へ置き換えることで、S_i を正しい括弧列にできるか？

入力

入力は以下の形式で標準入力から与えられる。

N
S
Q
l_1 r_1
l_2 r_2
:
l_Q r_Q
  • 1 行目には、文字列の長さ N (1≦N≦10^5) が与えられる。
  • 2 行目には、長さ N の文字列 S が与えられる。S は (，)，? のみからなる。
  • 3 行目には、質問の個数 Q (1≦Q≦10^5) が与えられる。
  • 4 行目からの Q 行には、質問の情報が与えられる。このうち i 行目には、整数 l_i と r_i (1≦l_i≦r_i≦N) が空白区切りで与えられる。

出力

Q 行出力せよ。i 行目には、i 番目の質問に対する答えとして Yes または No を出力せよ。

入力例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

Problem

We prefer correct parenthesis sequences. Correct parenthesis sequences are defined as follows.

  1. An empty string is a correct parenthesis sequence.
  2. If string s is a correct parenthesis sequence, (+s+) is also a correct parenthesis sequence.
  3. If string s and t are correct parenthesis sequences, s + t is also a correct parenthesis sequence.

You have a string S with length N. S consists only of (, ), and ?.

Your task is to answer Q questions about string S. The i-th question is as follows:

  • Let S_i be the substring of S from the l_i-th character to the r_i-th character, inclusive. Is it possible to make S_i a correct parenthesis sequence by replacing every occurrence of ? with ( or )?

Input

The input is given from the standard input in the following format.

N
S
Q
l_1 r_1
l_2 r_2
:
l_Q r_Q
  • In the first line, integer N (1≦N≦10^5) is written, which indicates the length of string S.
  • In the second line, string S is written. S consists only of (, ), and ?.
  • In the third line, integer Q (1≦Q≦10^5) is written, which indicates the number of questions.
  • The subsequent Q lines describe the questions. The i-th line among them contains two integers l_i and r_i (1≦l_i≦r_i≦N), separated by a space.

Output

Output Q lines. In the i-th line, print Yes or No, according to the answer to the i-th question.

Input Example 1

4
?()?
6
1 2
2 3
3 4
1 3
2 4
1 4

Output Example 1

No
Yes
No
No
No
Yes

Input Example 2

10
(?)?)?(?))
10
2 2
6 9
6 7
3 5
4 8
2 9
1 2
6 8
2 4
1 4

Output Example 2

No
Yes
No
No
No
Yes
Yes
No
No
Yes