Sereja và Mảng

Cho một mảng gồm $n$ số nguyên $a_1,a_2,\dots ,a_n$. Bạn cần thực hiện $m$ thao tác, mỗi thao tác thuộc một trong ba loại sau:

1. 1 $v$ $x$: gán $a_v=x$ (đặt phần tử thứ $v$ bằng $x$).
2. 2 $y$: tăng mọi phần tử của mảng thêm $y$, tức là $a_i=a_i+y$ với mọi $1\le i\le n$.
3. 3 $q$: in ra giá trị hiện tại của phần tử $a_q$.

Hãy thực hiện tất cả các thao tác theo đúng thứ tự đã cho.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $m$ dòng tiếp theo, mỗi dòng mô tả một thao tác:
  • Nếu bắt đầu bằng số $1$: theo sau là hai số nguyên $v$ và $x$.
  • Nếu bắt đầu bằng số $2$: theo sau là một số nguyên $y$.
  • Nếu bắt đầu bằng số $3$: theo sau là một số nguyên $q$.

Dữ liệu ra

Với mỗi thao tác loại $3$, in ra giá trị $a_q$ trên một dòng riêng, theo đúng thứ tự các truy vấn xuất hiện trong dữ liệu vào.

Ràng buộc

• $1\le n,m\le {10}^5$
• $1\le a_i\le {10}^9$
• $1\le v\le n$, $1\le x\le {10}^9$
• $1\le y\le {10}^4$
• $1\le q\le n$

Ví dụ