L. BBS Queries
time limit per test
4 с
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a balanced bracket sequence of only $$$'('$$$ and $$$')'$$$ brackets of length $$$2n$$$, a value of $$$a_i$$$ is attached to every bracket, and for every two matched pair of brackets, they have the same value

For example, let the balanced bracket sequence be: $$$()(())()$$$ and the array $$$a$$$: $$$[1, 1, 5, 1, 1, 5, 2, 2]$$$, Notice that values at indexes $$$1$$$ and $$$2$$$ are same because the bracket of index $$$2$$$ is the one that closes the bracket at index $$$1$$$, values at indexes $$$3$$$ and $$$6$$$ are same because the bracket of the index $$$6$$$ is the one the closes the bracket at index $$$3$$$, and so on for every two matched pair in the balanced bracket sequence

You are also given two types of queries:

The query of type $$$1$$$ is as follows: $$$1$$$ $$$l_1$$$ $$$r_1$$$ $$$l_2$$$ $$$r_2$$$ $$$v$$$, where $$$l_1$$$ and $$$r_1$$$ are indexes of two matched brackets, $$$l_2$$$ and $$$r_2$$$ are also indexes of two matched brackets, in such query you have to add a value of $$$v$$$ to the value of every two matched brackets which their opening bracket is before or equal to $$$\min(l_1, l_2)$$$ and closing bracket is after or equal to $$$\max(r_1, r_2)$$$

Please note that it isn't necessary that $$$l1 \le l2$$$ nor $$$r1 \le l2$$$

The query of type $$$2$$$ is as follows: $$$2$$$ $$$l$$$ $$$r$$$, where $$$l$$$ and $$$r$$$ are indexes of two matched brackets, in such query you have to find the value of these two brackets, (note that always any two matched brackets will have the same value and you are asked to find this value, not the sum of values of the two brackets)

Refer to the notes and check the described example for better understanding

A balanced bracket sequence is a string consisting of only brackets, such that this sequence when inserted with certain numbers and mathematical operations, gives a valid mathematical expression

Input

The first contains an integer $$$t$$$ $$$( 1 \le t \le 10^{5} )$$$ the number of testcases

In every test case you will read two integers $$$(1 \le n \le 5*10^{5})$$$ and $$$(1 \le q \le 5*10^{5})$$$, where $$$2n$$$ is the length of the string and $$$q$$$ is the number of queries

The second line of every testcase contains the string of brackets balanced bracket sequence, the length of the string is $$$2n$$$,

The third line of every testcase contains the array $$$a$$$ $$$(0 \le a_i \le 10^{9})$$$, the values attached to the brackets

The following $$$q$$$ lines contains the $$$q$$$ queries

It's guaranteed that all $$$ls$$$ and $$$rs$$$ in queries are between $$$1$$$ and $$$2n$$$, and the string forms a balanced bracket sequence with brackets of type $$$()$$$ only (doesn't contains brackets of other types like $$$[]$$$ or $$${}$$$)

It's guaranteed that the sum of $$$n$$$ and $$$q$$$ all test cases don't exceed $$$5*10^{5}$$$

Output

For every testcase, for each query of type $$$2$$$ you have to print its answer as described above

Example
Input
1
5 4
(()(())())
3 1 1 5 1 1 5 2 2 3
2 4 7
1 2 3 4 7 5
2 1 10
2 2 3
Output
5
8
1
Note

Description of the given sample:

First query: $$$4$$$ $$$7$$$

The value of the matched pair at indexes $$$4$$$ and $$$7$$$ is $$$5$$$

Second query: $$$2$$$ $$$3$$$ $$$4$$$ $$$7$$$ $$$5$$$

The matched pair at indexes $$$1$$$ $$$10$$$ is the only matched pair of brackets that includes pairs $$$2$$$ $$$3$$$ and $$$4$$$ $$$7$$$ together, hence we increase its value by $$$5$$$ and the array of values after this query becomes: $$$8$$$ $$$1$$$ $$$1$$$ $$$5$$$ $$$1$$$ $$$1$$$ $$$5$$$ $$$2$$$ $$$2$$$ $$$8$$$

Third query: $$$1$$$ $$$10$$$

The value of the matched pair at indexes $$$1$$$ $$$10$$$ is $$$8$$$

Forth query: $$$2$$$ $$$3$$$

The value of the matched pair at indexes $$$2$$$ $$$3$$$ is $$$1$$$