Cho dãy số nguyên (\(a_1, a_2,.., a_n\)), ban đầu tất cả phần tử của dãy \(A\) được đặt bằng \(0\). Xét dãy gồm \(m\) lệnh mỗi lệnh thuộc \(2\) loại:

• \(S(i, k):\) Đặt \(a_i = k\)
• \(Q(i, j):\) Cho biết tổng các phần tử từ \(a_i\) tới \(a_j\).

Yêu cầu: Trả lời các truy vấn \(Q\).

Input

• Vào từ file văn bản QUERYSUM.INP
• Dòng \(1\) chứa hai số nguyên dương \(n, m \le 10^5\).

• \(m\) đòng tiếp theo, mỗi dòng mô tả một lệnh: Đầu dòng là một chữ cái \(\in\) {\(S\), \(Q\)} cho biết loại lệnh

  • Nếu ký tự đầu dòng là \(S\): Tiếp theo là dấu cách và hai số nguyên dương \(i, k\) cách nhau bởi dấu cách \((i \le n, k \le 10^9)\)
  • Nếu ký tự đầu dòng là \(Q\): Tiếp theo là dấu cách và hai số nguyên dương \(i, j\) cách nhau bởi dấu cách \((i \le j \le n)\)

Output

• Ghi ra file văn bản QUERYSUM.OUT, với mỗi một lệnh \(Q\) ghi một số nguyên duy nhất là đáp số trên một dòng.

Example

5 7
S 1 1
S 2 2
S 3 3
Q 2 4
S 4 4
S 3 1
Q 1 5

5
8