Nhập vào một mảng chứa \(n\) số nguyên. Cần trả lời \(q\) truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

1. Tăng giá trị của tất cả các phần tử trong đoạn \([l,\ r]\) lên \(v\) đơn vị;
2. In ra giá trị của phần tử tại vị trí \(p\).

Input

• Dòng đầu chứa hai số nguyên \(n\) và \(q\): lần lượt là kích thước của mảng và số lượng truy vấn;
• Dòng thứ hai chứa \(n\) số nguyên \(x_1,\ x_2,\ldots,\ x_n\): giá trị của các phần tử trong mảng;
• Cuối cùng là \(q\) dòng mô tả \(q\) truy vấn. Mỗi truy vấn có dạng "\(1\ l\ r\ v\)" hoặc "\(2\ p\)".

Output

• Với mỗi truy vấn loại \(2\), in ra kết quả trên một dòng.

Ràng buộc

• \(1\leq n,\ q\leq2\times10^5\);
• \(1\leq x_i,\ v\leq10^9\);
• \(1\leq p\leq n\);
• \(1\leq l\leq r\leq n\).

Ví dụ

Sample input

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

Sample output

5
6