As is well known, a heap is a data structure that can efficiently extract the minimum value, with its key operations being "up-heap" (or bubble-up) and "down-heap" (or bubble-down).

Specifically, a heap is a binary tree structure stored linearly in an array Heap[1..n], where the weight of node $i$ ($1 \le i \le n$) is Heap[i], its left child is $2i$, and its right child is $2i + 1$, satisfying Heap[i] <= min{Heap[2i], Heap[2i + 1]}.

To perform the up-heap operation on node $x$ ($1 \le x \le n$), we repeatedly compare node $x$ with its parent's weight and swap them if the child is smaller. The C++ code is as follows:

void Up(int x):
while(x>1 && Heap[x]<Heap[x>>1]){
    swap(Heap[x],Heap[x>>1]);
    x>>=1
}

To perform the down-heap operation on node $x$ ($1 \le x \le n$), the C++ code is as follows:

void Down(int x):
while(x*2<=n){
    int y=x*2;
    if (y<n && Heap[y+1]<Heap[y]) y++;
    if (Heap[y]>=Heap[x])break;
    swap(Heap[x],Heap[y]);
    x=y;
}

An $O(n)$ algorithm to build a heap is: for an array h[1..n] of $n$ elements, perform the down-heap operation on each node in order from $n$ down to $1$ to obtain a heap of $n$ nodes.

Given a permutation $a$ of length $n$ and $q$ queries, there are two types of queries:

The first type of query provides an interval $[l, r]$ ($1 \le l \le r \le n$) and a number $x$ ($1 \le x \le r - l + 1$). After applying the aforementioned $O(n)$ heap construction algorithm to the subsequence $a[l..r]$, find the weight of node $x$. Specifically, for $1 \le i \le r - l + 1$, let $b[i] = a[l + i - 1]$, build a heap of $r - l + 1$ nodes using $b$ as the weights, and find the weight of node $x$ in the heap.

The second type of query also provides an interval $[l, r]$ ($1 \le l \le r \le n$) and a number $x$ ($1 \le x \le n$), where $x$ is guaranteed to be an element in $a[l..r]$. After applying the same algorithm to the subsequence $a[l..r]$, find the index of the node with weight $x$. Specifically, for $1 \le i \le r - l + 1$, let $b[i] = a[l + i - 1]$, build a heap of $r - l + 1$ nodes using $b$ as the weights, and find the index of the node with weight $x$ in the heap.

Input

The first line contains two integers $n$ and $q$.

The second line contains $n$ integers $a[1], \dots, a[n]$, representing a permutation of $n$.

The next $q$ lines each contain four integers $ty, l, r, x$, where $ty$ represents the type of query, $l$ and $r$ represent the chosen interval, and $x$ is the corresponding node index or weight.

Output

Output $q$ lines, each containing the answer to the corresponding query.

Examples

Input 1

7 10
5 3 2 1 4 6 7
1 5 7 3
1 3 7 5
1 4 5 2
2 5 7 6
2 6 7 7
1 1 5 2
2 3 3 2
2 7 7 7
2 1 6 1
2 3 7 2

Output 1

7
7
4
2
2
3
1
1
1
2

Constraints

$n, q \le 1 \times 10^5$

It is guaranteed that $a$ is a permutation of $1, \dots, n$.

Subtask 1 (30 pts): $n, q \le 1000$

Subtask 2 (20 pts): Only query type 1

Subtask 3 (20 pts): Only query type 2

Subtask 4 (20 pts): $n, q \le 5 \times 10^4$

Subtask 5 (10 pts): No special restrictions