13:I[87,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"Header"] 14:I[1742,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"ProblemView"] 15:T715,

This is an unusual problem in an unusual contest, here is the announcement: http://codeforces.com/blog/entry/73543

You 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.

Input

The 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$$$ ($$$

Segment tree or Fenwick?

Examples