[Solution] Changing Brackets solution codeforces | Codeforces Round #748

Changing Brackets solution codeforces


A sequence of round and square brackets is given. You can change the sequence by performing the following operations:

  1. change the direction of a bracket from opening to closing and vice versa without changing the form of the bracket: i.e. you can change ‘(‘ to ‘)‘ and ‘)‘ to ‘(‘; you can change ‘[‘ to ‘]‘ and ‘]‘ to ‘[‘. The operation costs 00 burles.
  2. change any square bracket to round bracket having the same direction: i.e. you can change ‘[‘ to ‘(‘ but not from ‘(‘ to ‘[‘; similarly, you can change ‘]‘ to ‘)‘ but not from ‘)‘ to ‘]‘. The operation costs 11 burle.

Changing Brackets solution codeforces

The operations can be performed in any order any number of times.

You are given a string ss of the length nn and qq queries of the type “l r” where 1l<rn1≤l<r≤n. For every substring s[lr]s[l…r], find the minimum cost to pay to make it a correct bracket sequence. It is guaranteed that the substring s[lr]s[l…r] has an even length.

The queries must be processed independently, i.e. the changes made in the string for the answer to a question ii don’t affect the queries jj (j>ij>i). In other words, for every query, the substring s[lr]s[l…r] is given from the initially given string ss.

Changing Brackets solution codeforces

A correct bracket sequence is a sequence that can be built according the following rules:

  • an empty sequence is a correct bracket sequence;
  • if “s” is a correct bracket sequence, the sequences “(s)” and “[s]” are correct bracket sequences.
  • if “s” and “t” are correct bracket sequences, the sequence “st” (the concatenation of the sequences) is a correct bracket sequence.

E.g. the sequences “”, “(()[])“, “[()()]()” and “(())()” are correct bracket sequences whereas “(“, “[(])” and “)))” are not.

Changing Brackets solution codeforces

Input

The first line contains one integer tt (1t1001≤t≤100) — the number of test cases. Then tt test cases follow.

For each test case, the first line contains a non-empty string ss containing only round (‘(‘, ‘)‘) and square (‘[‘, ‘]‘) brackets. The length of the string doesn’t exceed 106106. The string contains at least 22 characters.

The second line contains one integer qq (1q21051≤q≤2⋅105) — the number of queries.

Then qq lines follow, each of them contains two integers ll and rr (1l<rn1≤l<r≤n where nn is the length of ss). It is guaranteed that the substring s[lr]s[l…r] has even length.

It is guaranteed that the sum of the lengths of all strings given in all test cases doesn’t exceed 106106. The sum of all qq given in all test cases doesn’t exceed 21052⋅105.

Changing Brackets solution codeforces

Output

For each test case output in a separate line for each query one integer xx (x0x≥0) — the minimum cost to pay to make the given substring a correct bracket sequence.

Example
input

Copy
3
([))[)()][]]
3
1 12
4 9
3 6
))))))
2
2 3
1 4
[]
1
1 2
output

Copy
0
2
1
0
0
0

Changing Brackets solution codeforces


Note

Consider the first test case. The first query describes the whole given string, the string can be turned into the following correct bracket sequence: “([()])()[[]]“. The forms of the brackets aren’t changed so the cost of changing is 00.

The second query describes the substring “)[)()]“. It may be turned into “(()())“, the cost is equal to 22.

The third query describes the substring “))[)“. It may be turned into “()()“, the cost is equal to 11.

The substrings of the second test case contain only round brackets. It’s possible to prove that any sequence of round brackets having an even length may be turned into a correct bracket sequence for the cost of 00 burles.

In the third test case, the single query describes the string “[]” that is already a correct bracket sequence.

 


Changing Brackets solution codeforcesYet another MEX problem solution codechefYet another MEX problem solution codechefYet another MEX problem solution codechef

Leave a Comment