実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
正しい括弧列とは、以下で定義される文字列のことです。
- 空文字列は正しい括弧列である。
- 文字列 s が正しい括弧列であるとき、
(
+s+)
は正しい括弧列である。 - 文字列 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.
- An empty string is a correct parenthesis sequence.
-
If string s is a correct parenthesis sequence,
(
+s+)
is also a correct parenthesis sequence. - 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