题目背景

北北的面前出现了一个数组，他想给这个数组加上几个操作：单点加，区间查询。

题目描述

有一个长度为 $4\times 10^{18}$，下标范围为 $[-2\times 10^{18},2\times 10^{18})$ 的数组，一开始所有值均为 $0$，你要支持两种操作：

1. 若 $op$ 为 $1$，则输入 $x,k$，将 $a_x$ 加上 $k$ 。
2. 若 $op$ 为 $2$，则输入 $l,r$，询问 $[l,r]$ 之间的数之和。

共执行 $m$ 次。

输入输出

输入

第一行两个正整数，表示 $m$。

下面有 $m$ 行，每行三个正整数，输入如题目描述。

输出

若 $op=2$，输出一行正整数，表示答案。

样例

3
1 2 1
1 3 1
2 1 3

2

数据范围

$2\times-10^{18}<l,r,x<2\times 10^{18},m<10^5,k<3,op=$ {$1,2$}

特殊性质：对于 $33$% 的数据，前一半操作 $op=1$，后一半操作 $op=2$。

保证 $l,r$ 均在 $(-10^{18},10^{18})$ 之间。

如果你认为你的代码复杂度没错，但是 $TLE$，可以在头文件下加上这个：

#define fastcall __attribute__((optimize("-O3")))
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

虽然提高不了多少效率

友情提示：用 $STL$ 会因常数大而 $TLE$，建议手写。