After observing the transit of Venus, Dr. Picks designed a complex resistor. To simplify the problem, the constants used here differ from those in the real world.
There are $n$ independent cylindrical water tanks, numbered $1$ to $n$, each with a base area of $1 \, \text{m}^2$. Each tank has a valve at the top and a valve at the bottom, both allowing water to flow at a rate of $1 \, \text{m}^3/\text{s}$. The top valve is connected to a water source that provides an infinite supply of water, while the bottom valve is open to the environment, allowing water to drain out. Both the top and bottom of the tank have electrical interfaces, and the resistivity of the water is $1 \, \Omega \cdot \text{m}$.
The tanks are sufficiently tall, and a conductive float rests on the water surface, connected to the top interface of the tank by a wire. Initially, the $i$-th tank contains $a_i \, \text{m}^3$ of water.
Dr. Picks needs to calibrate this complex resistor. He will perform the following five types of operations:
Open the top valves of all tanks with indices in the range $[l, r]$ for $x$ seconds, then close them.
Open the bottom valves of all tanks with indices in the range $[l, r]$ for $x$ seconds, then close them.
Connect the bottom valves of all tanks with indices in the range $[l, r]$ to the sea using a communicating vessel system such that each of these tanks contains exactly $x \, \text{m}^3$ of water, then close the valves and remove the connection.
Connect a power source with an electromotive force of $1 \, \text{V}$ (with no internal resistance) to the top and bottom interfaces of the $y$-th tank. Dr. Picks measures the current flowing through the power source and then removes it.
Since areas soaked by water leave visible water stains while unsoaked areas do not, Dr. Picks can measure the height of the water stain in the $y$-th tank to infer the maximum amount of water it has ever held, thereby saving on construction costs.
Now, he asks you to help him with the pre-experiment. Can you tell him the current measured in each measurement operation and the maximum amount of water recorded?
Input
The first line contains two integers: $n, m$.
The next line contains $n$ integers, where the $i$-th number represents the initial volume of water $a_i \, \text{m}^3$ in the $i$-th tank.
The next $m$ lines each describe an operation. The first number $t_i$ in the $i$-th line indicates the operation type:
If $t_i = 1$, it is followed by three integers $l_i, r_i, x_i$, representing opening the top interfaces of all tanks in the range $[l_i, r_i]$ for $x_i$ seconds.
If $t_i = 2$, it is followed by three integers $l_i, r_i, x_i$, representing opening the bottom interfaces of all tanks in the range $[l_i, r_i]$ for $x_i$ seconds.
If $t_i = 3$, it is followed by three integers $l_i, r_i, x_i$, representing connecting all tanks in the range $[l_i, r_i]$ to the sea so that each contains exactly $x_i \, \text{m}^3$ of water.
If $t_i = 4$, it is followed by one integer $y_i$, representing the measurement of the current through the power source when connected to the $y_i$-th tank.
If $t_i = 5$, it is followed by one integer $y_i$, representing the measurement of the water stain height in the $y_i$-th tank.
Output
For each operation where $t_i = 4$, output an integer representing the reciprocal of the current (in units of $A^{-1}$). If the current is infinite, output 0.
For each operation where $t_i = 5$, output an integer representing the water stain height in the $y_i$-th tank (in units of $m$).
Examples
Input 1
5 6 1 2 3 4 5 2 1 3 2 4 1 1 1 4 1 5 3 3 1 5 4 4 2
Output 1
0 3 4
Constraints
| Test Case | $n=$ | $m=$ | Notes |
|---|---|---|---|
| 1 | $1000$ | $1000$ | |
| 2 | $1000$ | $1000$ | |
| 3 | $10^5$ | $10^5$ | No operation 2 |
| 4 | $5 \times 10^5$ | $5 \times 10^5$ | No operation 2 |
| 5 | $10^5$ | $10^5$ | No operation 1 and 5 |
| 6 | $10^5$ | $10^5$ | No operation 1 |
| 7 | $5 \times 10^5$ | $5 \times 10^5$ | No operation 1 |
| 8 | $5 \times 10^5$ | $5 \times 10^5$ | No operation 5 |
| 9 | $10^5$ | $10^5$ | |
| 10 | $5 \times 10^5$ | $5 \times 10^5$ |
For all data: $1 \leq n, m \leq 5 \times 10^5, ~ 0 \leq a_i, x_i \leq 10^9, 1 \leq l_i \leq r_i \leq n, ~ 1 \leq y_i \leq n$.
Note
Physical formulas that may be useful:
Ohm's Law: $I = \frac{U}{R}$, where $I, U, R$ represent current, voltage, and resistance, respectively.
Resistivity formula: $R = \rho \frac{L}{S}$, where $R, \rho, L, S$ represent resistance, resistivity, length of the resistor, and cross-sectional area, respectively.