Cho một dãy số nguyên dương \(a_0, a_1, \dots, a_{N-1}\). Bạn cần thực hiện lần lượt \(Q\) truy vấn thuộc một trong hai loại dưới sau:

• 1 i v : Gán \(a_i=v\)
• 2 l r : Tổng các phần tử trong đoạn con liên tiếp \(a_l,a_{l+1},\dots,a_{r-1}\)

Input

• Dòng đầu chứa 2 số nguyên dương \(N,Q\).
• Dòng thứ 2 chứa \(N\) số nguyên dương \(a_i\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một trong 2 loại truy vấn trên.

Output

• Trả lời các truy vấn loại 2 l r trên một dòng.

Constraints

• \(1\le N,Q\le 2\cdot 10^5\)
• \(0\le i<N\)
• \(0\le a_i,v\le 10^9\)
• \(0\le l<r\le N\)

Example