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.

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.

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

5
9