这个游戏涉及将珠子放入盒子中。游戏的规则过于复杂，在此不便赘述，但你只需要知道，记录相邻盒子中珠子的数量对于游戏结果至关重要。

你的朋友请求你编写一个程序来帮助他每次都能赢得比赛。在游戏开始时，所有盒子都是空的。

输入格式

输入的第一行包含一个整数 $T$，表示进行的比赛场数。每场比赛开始时，会有一行描述 $B$、$P$ 和 $Q$，分别代表盒子的数量、放入请求的数量和查询请求的数量。

接下来有 $P + Q$ 行，每行要么是 P i a，表示在第 $i$ 号盒子中放入 $a$ 颗珠子；要么是 Q i j，表示查询第 $i$ 号到第 $j$ 号盒子（包含边界）中珠子的总数。

输出格式

对于每个查询请求，输出此时游戏中第 $a$ 号到第 $b$ 号盒子（包含边界）中珠子的总数。

数据范围

• $0 < T \leq 100$
• $0 < B \leq 100000$
• $0 < P \leq 30000$
• $0 < Q \leq 30000$
• $0 \leq a \leq 100$
• $0 < i \leq j \leq B$
• 注意：盒子编号从 1 开始。
• 这是一个 I/O 密集型问题。对于 Java 程序员，这意味着你应该使用 BufferedReader 进行输入读取（而不是 Scanner）。在打印之前，将所有输出构建在 StringBuilder 中并进行单次打印也是有益的。

样例

样例输入 1

1
7 5 3
P 2 1
P 3 3
P 4 7
Q 1 4
P 7 6
Q 4 4
P 6 4
Q 1 7

样例输出 1

11
7
21