Segment Tree Maintenance

This problem involves maintaining a segment tree. A segment tree is a special binary tree that satisfies the following properties:

1. Each node corresponds to an interval and has an integer weight.
2. The root node corresponds to the interval \([1, n]\).
3. If a node corresponds to \([l, r]\) and \(l < r\), then its left child covers \([l, m]\) and its right child covers \([m+1, r]\), where \(m = \lfloor\frac{l+r}{2}\rfloor\).
4. If a node corresponds to \([l, r]\) with \(l = r\), it is a leaf.
5. If a node is not a leaf, its weight equals the sum of its left and right children's weights.

The segment tree is built on an array whose leaf weights are initially 0. You need to process \(m\) operations. There are two types of operations:

• Operation 1: Given \(l, r, a\), for every \(x\) with \(l \le x \le r\), add \(a\) to the weight of the leaf corresponding to \([x, x]\). The weights of all non-leaf nodes are updated accordingly.
• Operation 2: Given \(l, r, a\), count how many nodes in the segment tree satisfy both of the following conditions:
  • The node's corresponding interval \([L, R]\) is completely contained in \([l, r]\) (i.e. \(l \le L\) and \(R \le r\)).
  • The node's weight is less than or equal to \(a\) (i.e. \(\le a\)).

inputFormat

The first line contains two integers \(n\) and \(m\): the number of leaves and the number of operations, respectively.

Each of the next \(m\) lines describes an operation. An operation is in one of the following two formats:

• "1 l r a" for Operation 1 (update operation): add \(a\) to each leaf in the interval \([l, r]\).
• "2 l r a" for Operation 2 (query operation): count the nodes whose corresponding intervals are completely inside \([l, r]\) and whose weight is \(\le a\).

outputFormat

For each query operation (Operation 2), output a single line containing the answer.

sample

3 3
1 1 3 5
2 1 3 5
2 2 3 10

3
2