Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là xử lí \(q\) truy vấn của các loại sau đây:

1. tăng mỗi giá trị trong đoạn \([a,b]\) thêm \(u\)
2. giá trị ở vị trí \(k\) là gì?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(q\): số lượng giá trị và truy vấn
• Dòng thứ hai có \(n\) số nguyên \(x_1, x_2,\ldots, x_n\): các giá trị của dãy
• Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng có ba số nguyên: hoặc "1 \(a\) \(b\) \(u\)" hoặc "2 \(k\)"

Constraints

• \(1 \leq n,q \leq 2\cdot 10^5\)
• \(1 \leq x_i,u \leq 10^9\)
• \(1 \leq k \leq n\)
• \(1 \leq a \leq b \leq n\)

Output

• In ra kết quả của mỗi truy vấn loại 2

Example

8 3
3 2 4 5 1 1 5 3
2 4
1 2 5 1
2 4

5
6