C. Segment tree or Fenwick?time limit per test2.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis is an unusual problem in an unusual contest, here is the announcement: http://codeforces.com/blog/entry/73543You are given an array A of length n, initially filled with zeros. You need to process q queries to the array, each of one of the following types:   1 x y: you need to assign A_x=y;  2 l r: you need to print \sum\limits_{i=l}^r A_i.  Furthermore, there are T independent tests you need to process.InputThe first line contains an integer T (1 \leq T \leq 10^5) — the number of test cases.Each test case description starts with two integers n, q (1 \leq n, q \leq 10^5) — the length of the array and the number of queries. The following q lines contain the description of queries: 1~x~y (1 \leq x \leq n, 0 \leq y \leq 10^9) for queries of the first type and 2~l~r (1 \leq l \leq r \leq n) for queries of the second type. It is guaranteed that the sum of n as well as the sum of q does not exceed 10^6.OutputFor each query of the second type print its result on a separate line.ExampleInput
2
6 5
2 1 6
1 3 2
2 2 4
1 6 3
2 1 6
5 3
1 3 7
1 1 4
2 1 5
Output
0
2
5
11

2
6 5
2 1 6
1 3 2
2 2 4
1 6 3
2 1 6
5 3
1 3 7
1 1 4
2 1 5

0 2 5 11 
['data structures']