Fenwick Tree 2

Problem Description

There are $n$ numbers $a_1, a_2, a_3, \dots, a_n$, all initially $0$.

You must support $q$ operations:

1. 1 l r d: add $d$ to every $a_i$ with $l \le i \le r$.
2. 2 x: output $\left(\sum_{i=1}^{x} a_i\right) \bmod 2^{64}$.

Input Format

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \times 10^5$).

The following $q$ lines each describe an operation of the form 1 l r d or 2 x, with $1 \le x \le n$, $1 \le d \le 10^9$, and $1 \le l \le r \le n$.

Output Format

For each query, output one line containing the answer.

Sample Input

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

Sample Output

10
21

Constraints

$1 \le n, q \le 2 \times 10^5$, $1 \le d \le 10^9$, $1 \le x \le n$, $1 \le l \le r \le n$.