Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Cho \(Q\) thao tác thực hiện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(p_i\) \(x_i\): Tăng phần tử ở vị trí \(p_i\) lên \(x_i\) đơn vị.
• \(2\) \(u_i\) \(v_i\): Tính tổng các phần tử từ vị trí \(u_i\) tới vị trí \(v_i\).

Yêu cầu
Thực hiện tất cả lần lượt \(Q\) thao tác, và in ra kết quả của thao tác loại \(2\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((A_i \leq 10^9)\).
• \(Q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi hai số nguyên dương \(p_i\) và \(x_i\) \((1 \leq p_i \leq N\), \(1 \leq x_i \leq 10^4)\). Số \(2\) theo sau bởi hai số nguyên dương \(u_i\) và \(v_i\) \((1 \leq u_i \leq v_i \leq N)\).

Output

• Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra tổng các phần atử từ vị trí \(u\) tới vị trí \(v\) trên một dòng.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 10^3\), \(Q \leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\).

Example

6 5
9 2 4 7 4 8
1 5 6
2 1 5
1 3 8
1 2 3
2 2 4 

32
24

Cho dãy \(a\) gồm \(n\) phần tử là các số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\). Cho \(q\) thao tác thực hiện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(u_{i}\) \(v_{i}\) \(x_{i}\): Tăng mỗi phần tử từ vị trí \(u_{i}\) tới vị trí \(v_{i}\) lên \(x_{i}\) đơn vị.
• \(2\) \(u_{i}\) \(v_{i}\): Tính tổng các phần tử từ vị trí \(u_{i}\) tới vị trí \(v_{i}\).

Yêu cầu: thực hiện tất cả lần lượt \(q\) thao tác, và in ra kết quả của thao tác loại \(2\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(n, q\) \((1 \leq n, q \leq 10^{5})\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) \((a_{i} \leq 10^{9})\).
• \(q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi ba số nguyên dương \(u_{i}\), \(v_{i}\) và \(x_{i}\) \((1 \leq u_{i} \leq v_{i} \leq n, 1 \leq x_{i} \leq 10^{9})\). Số \(2\) theo sau bởi hai số nguyên dương \(u_{i}\) và \(v_{i}\) \((1 \leq u_{i} \leq v_{i} \leq n)\).

Output

• Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra tổng các phần tử từ vị trí \(u\) tới vị trí \(v\) trên một dòng.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, q \leq 10^{3}\).
• Subtask \(2\) (\(30\%\) số điểm): mọi thao tác loại \(1\) có \(u = v\).
• Subtask \(3\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

5 4
1 4 6 2 3
2 1 4
1 2 5 3
1 3 4 5
2 3 5 

13
30

Có \(n\) hộp kẹo, hộp thứ \(i\) có \(a_i\) viên và tất cả \(m\) người lần lượt tới ăn. Người thứ \(i\) sẽ chỉ ăn kẹo ở các hộp có số lượng còn lại không ít hơn \(t_i\) chiếc và sẽ ăn ở những hộp này, mỗi hộp một viên.

Yêu cầu: Hãy xác định số kẹo từng người đã ăn.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(n\le 10^5\)),
• Dòng thứ 2 chứa \(n\) số nguyên dương \(a_1,a_2,…,a_n\) (\(a_i\le 10^9\))
• Dòng thứ 3 chứa số nguyên dương \(m\) (\(m\le 10^5\)),
• Dòng thứ 4 chứa \(m\) số nguyên dương \(t_1,t_2,…,t_M\) (\(t_i\le 10^9\)),

Output

• Đưa ra m số nguyên, mỗi số trên một dòng. Số thứ \(i\) là số viên kẹo người thứ \(i\) đã ăn.

Example

3
3 1 1
2
1 2

3
1

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