Cho một mảng gồm \(N\) phần tử \(a[1],a[2],...,a[N]\) và có \(T\) truy vấn có dạng như sau:

• \(1\text{ }l\text{ }r\): In ra tổng tất cả các phần tử thuộc đoạn \([l,r]\)
• \(2\text{ }x\text{ }y\): Thay giá trị tại vị trí thứ \(x\) thành \(y\) (tức là gán \(a[x]=y\))

Input

• Dòng thứ nhất chứa hai số nguyên \(N,T\)
• Dòng thứ hai chứa \(N\) số nguyên \(a[1],a[2],...,a[N]\) \((1\leq a_i\leq 10^5)\)
• \(T\) dòng tiếp theo chứa \(T\) truy vấn: \(1 \text{ }l\text{ }r\) \((1\leq l\leq r\leq n)\) hoặc \(2\text{ }x\text{ }y\) \((1\leq x\leq N, 1\leq y\leq 10^4)\)

Output

• Ứng với mỗi truy vấn \(1\text{ }l\text{ }r\) in ra tổng cần tìm

Constraints

• \(1\le N\le 10^4\)
• \(1\le T\le 10^5\)

Example

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

5
6