Brackets

Miceren likes playing with brackets.

There are $N$ brackets on his desk forming a sequence. In his spare time, he will do $Q$ operations on this sequence, each operation is either of these two types:

1. Flip the $X$-th bracket, i.e. the $X$-th bracket will become ) if it is ( before, otherwise become ( .

2. In a given subsequence $[L,~R]$, query the $K$-th bracket position number after deleting all matched brackets. If the amount of brackets left is less than $K$, output -1.
For example, if $N$ = 10, $L$ = 2, $R$ = 9 and the sequence is ))(()))((). In the sub sequence [2, 9], the brackets sequence is )(()))((. After deleting all matched brackets, the sequence becomes ) )((. If $K$ = 1, answer is 2. If $K$ = 2, answer is 7. If $K$ = 3, answer is 8. If $K$ = 4, answer is 9. If $K~\ge~5$, answer is -1.

Miceren is good at playing brackets, instead of calculating them by himself.

As his friend, can you help him?

The first line contains a single integer $T$, indicating the number of test cases.

Each test case begins with two integers $N,~Q$, indicating the number of brackets in Miceren's desk and the number of queries.

Each of following $Q$ lines describes an operation: if it is "1 X", it indicate the first type of operation. Otherwise it will be "2 L R K", indicating the second type of operation.

$T$ is about 100.

$1~\le~N, Q~\le~200000.$

For each query, $1~\le~X~\le~N$ and $1~\le~L~\le~R~\le~N$, $1~\le~K~\le~N$.

The ratio of test cases with $N~\gt~100000$ is less than 10%.

For each query operation, output the answer. If there is no $K$ brackets left, output -1.

1
10 5
))(()))(()
2 2 9 2
2 2 9 3
2 2 9 5
1 3
2 2 9 5

7
8
-1
8

赛码"BestCoder"杯中国大学生程序设计冠军赛