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\leN, Q\le200000.$

For each query, $1\leX\leN$ and $1\leL\leR\leN$, $1\leK\leN$.

The ratio of test cases with $N\gt100000$ is less than 10%.

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