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,... 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\)".

Output

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

Constraints

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

Example

Input:

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

Output:

5
6