If you guard every place, your forces will be few everywhere.
- Sun Tzu, The Art of War, ''Weak Points and Strong''
You are a skilled military adviser who serves a general and plans the army's advance. The general's army intends to pass through several regions in order. It must leave garrisons behind without running short of troops for the onward march. Fortunately, soldiers in each region are ready to join the column.
The regions are numbered through . When the army passes through region , it first leaves soldiers there as a garrison. Immediately after doing so, at least one soldier must remain in the marching column. Only then do the region's soldiers join the column. Soldiers left in a garrison do not rejoin it.
The first line contains the number of regions and the number of commands , separated by a space.
The -th of the next lines contains and , separated by a space.
For each command of the second type, print the minimum required number of soldiers on its own line. If there are no such commands, print nothing.
For the first query in the first example, starting with soldiers allows the following march.
Information about the numbers of recruits and required garrison troops in each region changes constantly. Whenever new information arrives, you must update the plan and report how many soldiers are needed to pass through the regions specified by the general. Process the following two types of commands.
1 i a b: Change the number of recruits in region to , and the number of soldiers to leave as a garrison to .2 l r: Find the minimum number of soldiers the column must have on entering region in order to pass through regions through in increasing order of their numbers.For the second type of command, the rules above must hold in every specified region. At least one soldier must remain immediately after leaving the garrison in the last region as well. Each query is evaluated independently using the current plan; the army does not actually march. The plan changes only through commands of the first type.
Each of the next lines contains one command.
Starting with soldiers would leave nobody in the column immediately after assigning the garrison in region , violating the rules.
In the last query of the second example, the garrison of soldiers must be assigned before the recruits join. Therefore, the initial number of soldiers must be at least .