Simple Sum

Given an array with N elements, your task is to determine how to compute the sum of numbers within a specified segment.

Input Data

The first line of input consists of two integers, N and K, representing the number of elements in the array and the number of queries, respectively. (1 ≤ N ≤ 10^6); (1 ≤ K ≤ 10^5). The next K lines contain the queries, which are of two types:

1. A i x – Set the i-th element of the array to the value x (1 ≤ i ≤ N; 0 ≤ x ≤ 10^9).

2. Q l r – Calculate the sum of the elements in the array from position l to r. (1 ≤ l ≤ r ≤ N).

Initially, all elements of the array are zero.

Output Data

For each query of the form Q l r, output a single number representing the sum of the elements in the specified segment.

Examples