Q lệnh GET/SET trên mảng tĩnh

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một mảng tĩnh có logical size cố định

Xử lý tuần tự $q$ lệnh. Mỗi lệnh thuộc một trong hai dạng:

• GET p: in giá trị hiện tại $a_p$;
• SET p x: cập nhật $a_p\leftarrow x$ và không in gì.

Mọi chỉ số $p$ đều thỏa

Logical size $n$ không thay đổi trong suốt quá trình. Kết quả của một lệnh GET phải phản ánh toàn bộ các lệnh SET trước nó.

Input

Dòng đầu chứa $n,q$. Dòng thứ hai chứa $n$ phần tử ban đầu. Mỗi trong $q$ dòng tiếp theo là GET p hoặc SET p x.

Output

Với mỗi lệnh GET, in một dòng chứa giá trị hiện tại ở chỉ số được hỏi. Lệnh SET không tạo output.

Subtask

Subtask 1 (20 điểm): $1\le n,q\le10$.

Subtask 2 (30 điểm): $1\le n,q\le1000$.

Subtask 3 (50 điểm): $1\le n,q\le10^5$, $|a_i|,|x|\le10^9$.

Ví dụ

Input

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

Output

20
99
-5

Giải thích

Lệnh SET 1 99 thay đổi kết quả của lần GET 1 tiếp theo; tương tự với chỉ số 3.