I. Reactor
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In a high-tech industrial facility, a series of nuclear reactors are arranged in a linear configuration. Each reactor operates under strict pressure regulations to ensure safety and efficiency. To prevent critical failures, each reactor has a specific maximum pressure limit. When a reactor's internal pressure reaches or exceeds this limit, a controlled pressure release (venting) is initiated. This system requires sophisticated management due to dynamic operational adjustments and the need for continuous monitoring.

You are tasked with designing and implementing a system to manage the pressure of a line of $$$n$$$ reactors. Each reactor, indexed from $$$1$$$ to $$$n$$$, has an initial maximum pressure limit $$$p_i$$$. All of the reactors' initial pressure are $$$0$$$. The system must support two types of operations:

  1. Pressure Increase Operation: For a given range of reactors $$$[l, r]$$$, increase their pressure by $$$k$$$ units. If the pressure of any reactor in this range reaches or exceeds its maximum limit, it will vent, resetting its pressure to $$$0$$$. And the maximum pressure limit of the vented reactor will be updated to $$$\max(\lfloor\frac{p_{old}}{2}\rfloor, 1)$$$, where $$$p_{old}$$$ is the maximum pressure limit of the reactor before the current pressure increase operation.
  2. Venting Count Query: For a given range of reactors $$$[l, r]$$$, you need to report the total number of venting operations that have occurred among all reactors within this specified range since the beginning of the system's operation.
Input

The first line contains two integers $$$n$$$ and $$$q$$$, representing the number of reactors and the number of operations, respectively.

The second line contains $$$n$$$ integers, the $$$i$$$-th integer $$$p_i$$$ represents the initial maximum pressure limit of the $$$i$$$-th reactor.

The following $$$q$$$ lines describe the operations. Each line begins with an integer $$$op$$$.

  • If $$$op = 1$$$, it is followed by three integers $$$l$$$, $$$r$$$, and $$$k$$$, representing a pressure increase operation on the range of reactors from $$$l$$$ to $$$r$$$ (inclusive) by $$$k$$$ units.
  • If $$$op = 2$$$, it is followed by two integers $$$l$$$ and $$$r$$$, representing a venting count query for the range of reactors from $$$l$$$ to $$$r$$$ (inclusive).
  • $$$1 \leq n \leq 2 \times 10^5$$$
  • $$$1 \leq q \leq 2 \times 10^5$$$
  • $$$1 \leq p_i \leq 4\times 10^5$$$
  • $$$1 \leq l \leq r \leq n$$$
  • $$$1 \leq k \leq 4\times 10^5$$$
  • It is guaranteed that there is at least one Venting Count Query.
Output

For each query that $$$op = 2$$$, print a single integer on a new line, representing the total number of venting operations that have occurred among all reactors within the specified range since the beginning of the system's operation.

Examples
Input
10 5
5 10 23 45 10 45 65 10 68 9
1 5 10 664
1 2 9 5
2 4 10
1 8 8 5
2 1 10
Output
8
9
Input
10 10
79 26 9 28 13 40 26 54 69 19
1 1 5 6
1 5 7 2
2 4 7
1 9 10 19
2 5 7
1 5 7 27
2 10 10
2 9 9
1 6 6 20
1 3 8 6
Output
0
0
1
0
Input
10 10
56 29 49 42 47 21 23 54 8 31
2 9 9
1 5 6 23
2 6 7
2 4 7
1 5 6 68
2 1 9
2 3 6
1 2 10 89
2 6 8
1 3 6 53
Output
0
1
1
3
3
5