24327번 - СКОБИ 다국어

문제

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

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

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

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

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

입력

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

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

출력

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

제한

• 2 ≤ N ≤ 10⁵
• 1 ≤ T ≤ 10⁵
• 1 ≤ L_i ≤ R_i ≤ N за всяко 1 ≤ i ≤ Т

힌트