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?
Input
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%.
Output
For each query operation, output the answer. If there is no $K$ brackets left, output -1.
