EIU Programming Practices and Exams

Given an array of n positive integers and m queries. There are two types of queries that take the following form:

• 0 i:Delete element element at index i (value i will give the specific).
• 1 i: Output the value at index i.

Requests are made in order. If deletion fails, this request is ignored. Similarly, if there is no value at index i, output is -1.

Input

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

The second line contains positive integers in the given array, each value not exceeded 10^9.

The next m lines are m queries in the given form. The indices in the queries are less than or equal to n.

Output

Consists of many lines, the results of the second type queries

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