ILKQUERYIII  I LOVE KdTREES III
The "ILoveKdtrees'' annual con is receiving too many applicants so they decided to complicate a bit the task used to select participants. (They realized some people were using other data structures to solve their problems, so they designed this problem, almost only solvable with Kdtrees).
You are given a list of N numbers and Q queries.
Each query can be of two types.
Type0 queries (marked with 0 in the input), consist of three integers: i, l and k ; let d be the kth smallest element until the index i (i.e. if the first i +1 elements were sorted in nondescending way, d would be the element at index k  1 ). Then, the answer to each query is the index of the lth occurrence of d in the array. If there's no such index, the answer is 1.
Type1 queries (marked with 1 in the input) are contiguousswap updatequeries, and consists of a single integer i. When a type1 query is executed the elements at index i and i +1 in the list must be swapped.
You have to consider that all indexes are counted starting with 0.
Input
Input consists of one test case.
The first line contains two integers, N ( 1 ≤ N ≤ 10^{6}) and Q (1 ≤ Q ≤ 10^{5}).
The next line contains N possible distinct integers a_{i} ( 10^{9} ≤ ai ≤ 10^{9}).
Then Q lines follow. Each of them starts with an integer which can be 0 or 1, denoting the type of the query. If it’s 0, then three integers i, l and k follow (0 ≤ i < N, 1 ≤ k ≤ i+1, 1 ≤ l ≤ N).
If it’s 1, then an integer i follows, meaning that you have to swap the elements at indexes i and i+1 (0 ≤ i ≤ N1).
Output
For each query of type0 (in the same order as the input) output a single line with the answer to that query.
Example
Input: 10 6
2 3 1 1 2 7 9 1 2 6
0 2 3 2
1 1
1 2
0 2 3 2
1 0
0 0 2 1
Output: 8
7
2
hide comments
DK...:
20190507 23:41:50
@BerSub what we suppose to do with type 1 queries in which i=n1? 

Ankit Sultana:
20170908 16:28:06
There are test cases with i = n  1 for Type 1 Queries, which doesn't make any sense. 

mahmud2690:
20161214 07:22:55
As there is a problem with the input, for the 1type queries there cases I = N  1. 

Rishav Goyal:
20160817 11:08:09
will it pass O(Q(logn)^2) ? 

bsubercaseaux:
20160325 22:49:10
Ready ! :P 

[Rampage] Blue.Mary:
20160325 15:49:03
Where's the example Input/Output? 
Added by:  BerSub 
Date:  20160325 
Time limit:  0.400s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 