A segment tree is a special type of binary tree that satisfies the following properties:

Each node corresponds to an interval and has an integer weight.

The root node corresponds to the interval $[1, n]$.

If a node corresponds to the interval $[l, r]$ and $l < r$, then its left child and right child correspond to the intervals $[l, m]$ and $[m+1, r]$ respectively, where $m=\lfloor\frac{l+r}{2}\rfloor$.

If a node corresponds to the interval $[l, r]$ and $l = r$, then this node is a leaf.

If a node is not a leaf, its weight is equal to the sum of the weights of its left and right children.

Chtholly needs to maintain a segment tree where the initial weight of each leaf is $0$. There will be $m$ operations:

• Operation $1$: Given $l, r, a$, for each $x$ such that $l \leq x \leq r$, add $a$ to the weight of the leaf corresponding to $[x, x]$, and update the weights of the non-leaf nodes accordingly.
• Operation $2$: Given $l, r, a$, query how many nodes in the segment tree satisfy the condition that the interval corresponding to the node is contained within $[l, r]$ and its weight is less than or equal to $a$.

Input

The first line contains two integers $n$ and $m$.

The next $m$ lines each contain four integers $op, l, r, a$, representing an operation, where $op$ is the operation type.

Output

For each operation with $op=2$, output one line containing a single integer representing the answer.

Examples

Input 1

3 3
1 2 3 9
2 1 2 1
2 1 3 1

Output 1

1
1

Subtasks

Idea: zcysky,

Solution: nzhtl1477 ($O(m\sqrt{n\log n})$ solution), ccz181078 ($O(m\sqrt{n})$ solution)

Code: nzhtl1477 ($O(m\sqrt{n} \log n)$ code), ccz181078 ($O(m\sqrt{n\log n})$ code),

Data: nzhtl1477

For $100\%$ of the data, $1 \leq n, m \leq 10^5$, $1 \leq l \leq r \leq n$, $1 \leq op \leq 2$, $-10^5 \leq a \leq 10^5$.