线段树是一种特殊的二叉树，满足以下性质：

每个点和一个区间对应，且有一个整数权值；

根节点对应的区间是 $[1,n]$；

如果一个点对应的区间是 $[l,r]$，且 $l < r$，那么它的左孩子和右孩子分别对应区间 $[l,m]$ 和 $[m+1,r]$，其中 $m=\lfloor\frac{l+r}{2}\rfloor$；

如果一个点对应的区间是 $[l,r]$，且 $l=r$，那么这个点是叶子；

如果一个点不是叶子，那么它的权值等于左孩子和右孩子的权值之和。

珂朵莉需要维护一棵线段树，叶子的权值初始为 $0$，接下来会进行 $m$ 次操作:

• 操作 $1$：给出 $l,r,a$，对每个 $x$（$l\leq x\leq r$），将 $[x,x]$ 对应的叶子的权值加上 $a$，非叶节点的权值相应变化；
• 操作 $2$：给出 $l,r,a$，询问有多少个线段树上的点，满足这个点对应的区间被 $[l,r]$ 包含，且权值小于等于 $a$。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行包含四个整数 $op,l,r,a$，表示一次操作，其中 $op$ 表示操作类型。

输出格式

对每个 $op=2$ 的操作，输出一行，包含一个整数，表示答案

样例数据

样例输入

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

样例输出

1
1

子任务

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

对于 $100\%$ 的数据，$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$。