Bạn được cho một mảng gồm n số nguyên ban đầu: ~a₁, a₂, ..., aₙ~.

Có ~q~ truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

Loại 1: Cộng một giá trị ~u~ vào tất cả các phần tử trong đoạn chỉ số từ ~l~ đến ~r~ (bao gồm cả hai đầu mút).

Loại 2: Truy vấn giá trị hiện tại của phần tử tại vị trí ~k~.

Đầu vào:

Dòng đầu tiên chứa hai số nguyên n và q — số lượng phần tử trong mảng và số lượng truy vấn (~1 ≤ n, q ≤ 2⋅10^5~).

Dòng thứ hai chứa n số nguyên ~a₁, a₂, ..., aₙ~ — các phần tử ban đầu của mảng (~|aᵢ|~ ≤ ~10^9~).

Mỗi dòng trong số q dòng tiếp theo mô tả một truy vấn:

Nếu là loại 1, dòng sẽ có dạng: 1 l r u — cộng u vào tất cả các phần tử từ a[l] đến a[r] (1 ≤ l ≤ r ≤ n, |u| ≤ 10⁹).

Nếu là loại 2, dòng sẽ có dạng: 2 k — in ra giá trị hiện tại của a[k] (1 ≤ k ≤ n).

Đầu ra:

Với mỗi truy vấn loại 2, in ra một dòng chứa giá trị tương ứng.

Ràng buộc:

~1 \le n,q \le 2 \cdot 10^5~

~1 \le x_i, u \le 10^9~

~1 \le k \le n~

~1 \le a \le b \le n~

Ví dụ :

Input:

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

Output:

5
6