这是一次不寻常的比赛中的一个不寻常的问题,这里是公告:http://codeforces.com/blog/entry/73543
给你一个长度为 $$$n$$$ 的数组 $$$A$$$,最初用零填充。您需要处理对数组的 $$$q$$$ 查询,以下每种类型之一:
1. 1 x y:需要赋值$$$A_x=y$$$;
2. 2 l r:需要打印$$$\sum\limits_{i=l}^r A_i$$$。
输入
第一行包含一个整数 $$$T$$$ ($$$1 \leq T \leq 10^5$$$) — 测试用例的数量。
每个测试用例描述都以两个整数 $$$n, q$$$ ($$$1 \leq n, q \leq 10^5$$$) 开头 - 数组的长度和查询的数量。以下 $$$q$$$ 行包含查询的描述: $$$1~x~y$$$ ($$$1 \leq x \leq n$$$, $$$0 \leq y \leq 10^9$$$) 用于第一种类型的查询, $$$2~l~r$$$ ($$$1 \leq l \leq r \leq n$$$) 用于第二种类型的查询。
保证$$$n$$$的总和以及$$$q$$$的总和不超过$$$10^6$$$。
输出
对于第二种类型的每个查询,将其结果打印在单独的行上。
示例
输入 #1
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
输出 #1
0 2 5 11