13701370 SUSTech Online Judge

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 296  Solved: 139
[Submit][Status][Web Board]

Description

Linkedlist is a data structure that designed for efficient insertion or removal of elements. It has 3 basic operations: (1) insert(p, x), insert number x at position p. (Position counts starting from 1) (2) remove(p), remove the number at position p (3) query(p), return the number at position p.

Given a linkedlist with n numbers and there are m operations. You are only asked to output the result of each query(p).

It's kindly suggested that you can firstly solve it by singly linked list, and then doubly linked list.

Input

The fist line contains two integers n(1<=n<=1000) and m (1<=m<=1000), showing the number of elements and operations respectively.

The second line contains n integers, and the combat values will in the range of [0, 10^9].

The next m lines, each starts with 'i' (insert), 'r' (remove) or 'q' (query). Operation 'i', followed by two integers p and x, indicating you need to insert number x at position p. Operation 'r' and 'q', followed by one integer p, indicating the position you need to operate.

Output

Print each query result (the number at position p).

Sample Input

6 4
3 4 1 6 9 7
i 3 5
q 3
r 4
q 5

Sample Output

5
9

[Submit][Status]