Array Deletion Queries

Given an array of n positive integers and m queries.

There are two types of queries:

• 0 i: Delete the element at index i.
• 1 i: Output the value at index i.

Queries are processed in order.

If a deletion cannot be performed, the query is ignored. Similarly, if there is no value at index i, output -1.

Input

The first line contains two integers n and m (n, m <= 10^4).

The second line contains n positive integers representing the given array. Each value does not exceed 10^9.

The next m lines contain the queries in the given format.

The indices used in the queries are less than or equal to n.

Output

Output one line for each query of type 1, containing the requested value or -1 if there is no value at that index.

Example

Input

5 6
1 2 6 9 8
0 1
1 1
1 2
0 0
1 3
1 1

Output

6
9
-1
9