ILKQUERYIII - I LOVE Kd-TREES III


The "I-Love-Kd-trees'' 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 Kd-trees).

You are given a list of N numbers and Q queries. Each query can be of two types.

  • Type-0 queries (marked with 0 in the input), consist of three integers: i, l and k ; let d be the k-th smallest element until the index i (i.e. if the first i +1 elements were sorted in non-descending way, d would be the element at index k - 1). Then, the answer to each query is the index of the l-th occurrence of d in the array. If there's no such index, the answer is -1.
  • Type-1 queries (marked with 1 in the input) are contiguous-swap update-queries, and consists of a single integer i. When a type-1 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 ≤ 106) and Q (1 ≤ Q ≤ 105).

The next line contains N possible distinct integers ai (-109 ≤ ai ≤ 109).

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 ≤ N-1).

Output

For each query of type-0 (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
treenipples: 2021-05-13 21:25:22

Ignoring type-1 queries with i=n-1 results in AC. Not ignoring results in runtime error.

DK...: 2019-05-07 23:41:50

@BerSub what we suppose to do with type 1 queries in which i=n-1?

Ankit Sultana: 2017-09-08 16:28:06

There are test cases with i = n - 1 for Type 1 Queries, which doesn't make any sense.

mahmud2690: 2016-12-14 07:22:55

As there is a problem with the input, for the 1-type queries there cases I = N - 1.

Rishav Goyal: 2016-08-17 11:08:09

will it pass O(Q(logn)^2) ?

bsubercaseaux: 2016-03-25 22:49:10

Ready ! :-P

[Rampage] Blue.Mary: 2016-03-25 15:49:03

Where's the example Input/Output?


Added by:BerSub
Date:2016-03-25
Time limit:0.400s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY