Cho n số nguyên \(a_1,a_2, \ldots,a_n\). Hãy thực hiện \(Q\) truy vấn, mỗi truy vấn có \(1\) trong \(2\) dạng:

• \(1\) \(u\) \(v\) \(\Delta\): Tăng các giá trị \(a_u,a_{u+1},\ldots,a_v\) lên một lượng \(\Delta\)
• \(2\) \(k\): In ra giá trị \(a_k\)

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n,Q\) \((1 \leq n,Q\leq 2\times 10^5)\)
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\)
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn lần lượt thực hiện theo một trong hai dạng mô tả trên. Chú ý \(1 \leq \Delta \leq 10^9;1 \leq u \leq v \leq n;1 \leq k \leq n\)

Output

• Với mỗi truy vấn loại \(2\) in một số nguyên trên một dòng là kết quả tìm được

Example

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

5
6