Problem Description
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:
Flip the X-th bracket, i.e. the X-th bracket will become ) if it is ( before, otherwise become ( .
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 ≥ 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 ≤ N,Q ≤ 200000.
For each query, 1 ≤ X ≤ N and 1 ≤ L ≤ R ≤ N, 1 ≤ K ≤ N.
The ratio of test cases with N > 100000 is less than 10%.
Output
For each query operation, output the answer. If there is no K brackets left, output -1.
Sample Input
1
10 5
))(()))(()
2 2 9 2
2 2 9 3
2 2 9 5
1 3
2 2 9 5
Sample Output
7
8
-1
8
