Q GET/SET Operations on a Static Array

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem

Maintain a fixed-size array $A=(a_0,\ldots,a_{n-1})$ under $q$ operations. GET p prints the current $a_p$; SET p x assigns $a_p\leftarrow x$ and prints nothing. Every $p$ is valid and operations are processed in order.

Input

The first line contains $n,q$, the second line the initial array, followed by $q$ command lines.

Output

Print one line for each GET command.

Subtask

Subtask 1 (20 points): $1\le n,q\le10$.

Subtask 2 (30 points): $1\le n,q\le1000$.

Subtask 3 (50 points): $1\le n,q\le10^5$, values within $10^9$ in magnitude.

Example

Input

4 5
10 20 30 40
GET 1
SET 1 99
GET 1
SET 3 -5
GET 3

Output

20
99
-5

Explanation

Each GET observes all earlier SET operations.