СКОБИ

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

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

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

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

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

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

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

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

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