СКОБИ

시간 제한0.3초메모리 제한1024 MB

요약

괄호 문자열과 T개의 질의가 주어질 때, 각 부분 문자열이 올바른 괄호열인지 판별한다.

난이도: 보통10점 중 5점
유형: 누적 합, 스택, 문자열, 구현
정답자: 아직 제출이 없습니다

문제

Дадена е редица от N малки леви и десни скоби, номерирани с числата от 1 до N.

Можем да свързваме които и да било две скоби. Редицата от скоби е правилна, ако съществува свързване, при което:

Всяка лява скоба е свързана с точно една дясна скоба.
Всяка дясна скоба е свързана с точно една лява скоба.

Например редиците от скоби ( ), ( ( ) ( ) ), ( ) ( ( ( ) ( ) ) ( ) ) са правилни, докато редиците ( ) ), ) ( (, ( ( ) ( ) ( не са правилни.

Напишете програма skobi, която определя дали една редица от скоби е правилна или не е.

입력

На първия ред е числото N – броя на скобите в редицата. На следващия ред е самата редица, като между скобите няма разделители.

На третия ред е числото Т – броя на тестовете. На всеки от следващите T реда има по две числа Li и Ri, като за i-ят подред тест тези числа определят подредица на дадената, която започва от скобата с номер Li и завършва в скоба с номер Ri.

출력

За всеки тест от входа изведете на отделен ред е изхода по едно число: числото трябва да е едно, ако е съответната редица е правилна, или нула – ако не е правилна.

제한

2 ≤ N ≤ 105
1 ≤ T ≤ 105
1 ≤ Li ≤ Ri ≤ N за всяко 1 ≤ i ≤ Т

예제1

예제 1
입력
```
5
)()()
3
1 3
2 3
2 5
```
예상 출력
```
0
1
1
```