You are given a permutation ~p_1, p_2, \dots, p_N~ of ~1, 2, \dots, N~. Consider the following function:

void f(int l,int r) {
    if (l >= r) return;
    int i = min_element(p+l,p+r+1)-p; // position of minimum element in [l,r]
    rotate(p+l,p+i,p+i+1); // cyclically shift [l,i] to the right by 1, so that the minimum element gets moved to position l
    f(i+1,r); // continue on [i+1,r]
}

For example, calling ~f(1,N)~ on the permutation ~[4,2,1,3,6,5]~ gives a result of ~[1,4,2,3,5,6]~. Note that ~p~ remains a permutation of ~1, 2, \dots, N~ when ~f(1,N)~ is called on it several times.

Process ~Q~ queries of the form:

• 1: Call ~f(1,N)~ once.
• 2 i: Output the current value of ~p_i~.
• 3 i: Output the unique index ~j~ such that ~p_j = i~.

Constraints

~1 \le N, Q \le 3 \times 10^5~

~p_1, p_2, \dots, p_N~ is a permutation of ~1, 2, \dots, N~.

For all type 2 and type 3 queries, ~1 \le i \le N~.

Subtask 1 [10%]

~1 \le N, Q \le 5 \times 10^3~

Subtask 2 [10%]

~1 \le N \le 5 \times 10^3~

Subtask 3 [20%]

All type 1 queries appear before all type 2 and type 3 queries.

Subtask 4 [25%]

There are only type 1 and type 2 queries.

Subtask 5 [25%]

There are only type 1 and type 3 queries.

Subtask 6 [10%]

No additional constraints.

Input Specification

The first line contains two space-separated integers: ~N~ and ~Q~.

The second line contains ~N~ space-separated integers: ~p_1, p_2, \dots, p_N~.

The next ~Q~ lines each describe a query.

Output Specification

For each type 2 or type 3 query, output the answer on a new line.

Sample Input

6 16
4 2 1 3 6 5
3 1
3 2
3 3
3 4
3 5
3 6
1
2 1
2 2
2 3
2 4
2 5
2 6
1
2 3
3 3

Sample Output

3
2
4
1
6
5
1
4
2
3
5
6
4
4

Explanation

Initially, ~p~ is ~[4,2,1,3,6,5]~. We have

• ~1~ appears at index ~3~, so the answer to the first query is ~3~.
• ~2~ appears at index ~2~, so the answer to the second query is ~2~.
• ~3~ appears at index ~4~, so the answer to the third query is ~4~.
• ~4~ appears at index ~1~, so the answer to the fourth query is ~1~.
• ~5~ appears at index ~6~, so the answer to the fifth query is ~6~.
• ~6~ appears at index ~5~, so the answer to the sixth query is ~5~.

After calling ~f(1,N)~ once, ~p~ is ~[1,4,2,3,5,6]~.

After calling ~f(1,N)~ a second time, ~p~ is ~[1,2,4,3,5,6]~.