Virus Simulator

Time limit3sMemory limit1024 MB

Summary

Process virus spreads that pass between people, vaccinations, and range queries for the largest sum of a block of consecutive people with positive immunity.

Level: Hard8 of 10
Topics: Segment tree, Simulation
Solved: No attempts yet

Problem

In the spring of 2123, the Virus Simulator was finally released.

The Virus Simulator lets users set people's immunity and viruses' vitality, then run simulations directly. It was built to prepare for future virus outbreaks.

There are $N$ people in the simulator, numbered from $1$ to $N$ in order. The immunity of the $i$ -th person is $A_i$ .

You may perform one or more actions. There are three kinds: virus infiltration, vaccination, and group immunity measurement. Each action is given in the input as follows.

Virus infiltration: $1$ $i$ $x$ . A virus with vitality $x$ infiltrates person $i$ . The virus spends $1$ vitality to reduce the infected person's immunity by $1$ . If, before the virus dies, the infected person has no immunity (that is, immunity is $0$ ) or loses it, the virus moves to the person with the highest immunity among people numbered greater than the current infected person. If several people tie, the virus moves to the one with the smallest number. This repeats until the virus's vitality reaches $0$ or no one is left to transfer to. $(1 \le i \le N;1 \le x \le 10^{9})$
Vaccination: $2$ $i$ $x$ . Person $i$ receives a vaccine with potency $x$ , and their immunity increases by $x$ . $(1 \le i \le N;1 \le x \le 10^{9})$
Group immunity measurement: $3$ $l$ $r$ . People $l$ through $r$ form groups. Groups consist of adjacent people. People with no immunity form groups only with others who have no immunity, and people with immunity form groups only with others who have immunity. Among the groups formed, find the maximum sum of immunity among a group's members. $(1 \le l \le r \le N)$

Input

The first line contains two integers $N$ and $Q$ , the number of people and the number of actions, separated by a space. $(1 \le N, Q \le 200\,000)$

The second line contains $N$ integers $A_i$ , the immunity of each person, separated by spaces. $(1 \le A_i \le 10^{9})$

The next $Q$ lines each give one action in the format above.

At least one group immunity measurement action is given.

Output

For each group immunity measurement action, print the result on its own line.

Examples2

Example 1

Input

10 7
3 5 2 6 4 7 2 9 3 5
3 1 6
1 3 8
3 1 6
1 5 18
3 3 8
2 6 1
3 3 8

Expected output

Example 2

Input

9 8
6 3 5 2 3 1 2 3 2
1 2 10
1 2 5
1 3 2
3 2 8
1 7 2
2 4 10
1 3 6
3 2 9

Expected output

4
6