Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

EIUPH013 - Deletion và Queries

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

Added by:Ha Minh Ngoc
Date:2015-01-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NCSHARP GOSU JULIA PYPY3
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.