시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.3 초 1024 MB123231916.522%

문제

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

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

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

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

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

입력

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

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

출력

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

제한

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

예제 입력 1

5
)()()
3
1 3
2 3
2 5

예제 출력 1

0
1
1