Once, the kingdom of the North was attacked by the Westerlands. So, North got ready for battle with their army. Initially, all the members of the troop were walking in a single direction. But as the battle continued, they started to split in different directions. Each soldier is having a unique id. In each troop, the captain is the soldier with greatest ID. Now king needs to know the ID of captain for each soldier. Formally stating, there is a line of soldiers standing in increasing order of IDs. Two types of queries are coming.

• 1 x : The segment containing soldier with id x is divided into two segments, from starting of segment to x in one and rest in other.
• 2 id: Given the soldier id, you have to output id of its captain.

Input Format

The first line of the input contains N and Q denoting number of soldiers and total number of queries respectively.

The second line contains N integers denoting ids of soldiers, A₁, A₂, .... , A_N.

For next Q lines, each line contains a query.

The first integer denotes type of the query. For each query of type 1, next integer denote X. For each query of type 2, next integer denote id.

Constraints

• 2 ≤ N ≤ 10⁵
• 1 ≤ Q ≤ 10⁵
• 1 ≤ X, id, A[i] ≤ 10⁹

Output Format

For each query of type 2, output a single integer on a new line containing the id of his captain.