Cho số nguyên \(n\) và dãy số nguyên \(a_1,a_2,…,a_n\). Ban đầu tất cả các \(a_i=0\). Xét \(Q\) truy vấn, mỗi truy vấn có dạng sau:

• Loại 1: \(T(u,k)\) Thay \(a_u=k.\)

• Loại 2: \(H(u,v)\) Tính tổng các phần \(a_u+a_{u+1}+⋯+a_v.\)

Yêu cầu: In ra kết quả của truy vấn loại 2.

Input

• Dòng thứ nhất chứa \(n,Q (n,Q≤10^5 ).\)

• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn \(x\) \(u\) \(v\) với \(x\) là ký tự \(T\) tương ứng với truy vấn loại \(1\), \(x\) là ký tự \(H\) tương ứng với truy vấn loại \(2\). \((1≤u≤n,v≤10^9)\) với truy vấn loại \(1\), \(v≤n\) với truy vấn loại 2).

Output

• In ra kết quả truy vấn loại 2, mỗi truy vấn trên một dòng.

Sample Input

5 7
T 1 1
T 2 2
T 3 3
H 2 4
T 4 4
T 3 1
H 1 5

Sample Output

5
8