Zagrade

It is well known that the Central Intelligence Agency is tasked with gathering, processing, and analyzing national security information. It is also suspected that they own quite large collections of commonly used computer passwords and are developing sophisticated tools that can compromise password-protected computer systems.

The tables have turned. Your task is to compromise the security of a CIA server. Good luck!

Naturally, they are well aware of typical patterns that humans produce while coming up with their passwords, so attempts such as 123456, password, 1q2w3e4r, or welcome are futile. Luckily, we have uncovered certain pieces of information that might be of use to you.

Their master password consists of exactly N characters, where N is an even number. Exactly half of those characters are the open parenthesis ('('), while the other half are the closing parenthesis (')'). Also, instead of the usual "forgot your password?" functionality, their engineers have decided to expose an API to the forgetful administrator. Using the API, an administrator can execute at most Q queries asking "whether the interval of the password from the a-th to the b-th character is mathematically valid".

The mathematical validity of a sequence of parentheses is defined inductively as:

• () is a mathematically valid sequence.
• If A is a mathematically valid sequence, then (A) is a mathematically valid sequence as well.
• If both A and B are mathematically valid sequences, then AB is also mathematically valid.