树状数组2

题目描述

有$n$个数$a_1, a_2, a_3, \dots, a_n$，一开始都是$0$。

支持$q$个操作：

1. 1 l r d，令所有的$a_i (l\leq i \leq r)$加上$d$。
2. 2 x，查询$\left(\sum_{i=1} ^x a_i\right) \bmod 2^{64}$。

输入格式

第一行两个整数$n, q (1\leq n, q\leq 2\times 10^5)$。

接下来$q$行，每行一个形如1 l r d或者2 x的操作，保证$1\leq x\leq n, 1\leq d\leq 10^9, 1\leq l \leq r \leq n$。

输出格式

对于每个查询，输出一行，表示答案。

样例输入

5 5
1 2 3 1
1 1 5 2
2 4
1 1 3 3
2 5

样例输出

10
21