Energy Collection on Yae Street

Under the influence of the power of \(\text{绯玉丸}\), Yae Village has been transformed into an 8-length street known as Yae Street. In this street, \(\text{绯玉丸}\) can appear at any position along the street with Yae Sakura by her side. Meanwhile, Yae Sakura will dash through the street to collect the mysterious 嘤嘤嘤 energy at some positions to upgrade her \(\text{嘤嘤刀}\).

At every moment, one of the following 3 events occurs:

1. Event 1: 1 x val — At position \(x\), a mysterious entity \(\text{绯狱丸}\) appears carrying \(val\) units of energy. Immediately upon appearance, it swallows the energy at that position, so that the energy at position \(x\) becomes \(val - a_x\), where \(a_x\) is the energy at \(x\) just before the event. Also, position \(x\) is marked as containing a \(\text{绯狱丸}\) (flagged).
2. Event 2: 2 l r — \(\text{绯玉丸}\) appears with Yae Sakura at an arbitrary position in the interval \([l, r]\). Normally, Yae Sakura will collect the maximum energy among all positions in \([l, r]\). However, if there exists at least one position in \([l, r]\) that has a \(\text{绯狱丸}\) (i.e. has been flagged via Event 1), then she will ignore the normal energy and instead attack one of the \(\text{绯狱丸}\) to obtain its current energy. In such a case, the answer for the query is the maximum energy among those flagged positions in \([l, r]\).
3. Event 3: 3 l r val — \(\text{绯玉丸}\) uses her power to add \(val\) energy to every position in the interval \([l, r]\) (this includes positions that are flagged by Event 1).

You are given a street of length \(n\) with initial energy 0 at every position. Process \(q\) events in the order they are given. For every query of type 2, output the obtained energy.

Note: All formulas are written in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(q\) representing the length of the street and the number of events, respectively. The next \(q\) lines each contain an event in one of the following formats:

• 1 x val
• 2 l r
• 3 l r val

It is guaranteed that the events are valid. Initially, every position from 1 to \(n\) has energy 0.

outputFormat

For each event of type 2, output one line containing the corresponding energy value obtained as described in the problem.

sample

5 7
3 1 5 10
1 3 15
2 1 5
3 3 5 5
2 2 4
1 4 20
2 1 5

5
10
10