410037: GYM103921 I Cabinet Search

Bernardo just made an amazing lunch for himself, featuring his favorite dish, guacamole! He used a slew of ingredients along with his trusty molcajete, but now its time for him to clean up the mess he made while cooking. He has to hurry, though, in order to make it on time to his job (as a truck driver who transports large amounts of rocks and avocados across the country).

Because he is short on time, Bernardo needs to be efficient as he cleans up, so he will only perform $$$Q$$$ actions to tidy his kitchen.

Bernardo has $$$N$$$ cabinets in his kitchen lined up in a row. Initially, they are all closed, and can contain zero or more ingredients. For each integer $$$i$$$ such that $$$1 \leq i \leq Q$$$, Bernardo will perform an action, either:

• $$$1$$$ - Open the $$$x_i$$$th cabinet (it is guaranteed that the $$$x_i$$$th cabinet will be closed before this action).
• $$$2$$$ - Swap the number of ingredients in the $$$x_i$$$th and $$$y_i$$$th cabinets (these cabinets need not be open).
• $$$3$$$ - Add $$$y_i$$$ ingredients to the $$$x_i$$$th cabinet (this cabinet need not be open).
• $$$4$$$ - Move all ingredients from the $$$x_i$$$th cabinet to the $$$y_i$$$th cabinet (these cabinets need not be open).

After each of the $$$Q$$$ actions, your task is to calculate the length of the longest contiguous subarray of open cabinets as well as the maximum sum of the number of ingredients found within any contiguous subarray of open cabinets.

The input will begin with a line containing two space separated integers, $$$N$$$, and $$$Q$$$ ($$$1 \leq N, Q \leq 10^5$$$).

The next line will contain $$$N$$$ space separated integers, the $$$i$$$th of which, denoted by $$$x_i$$$ ($$$1 \leq x_i \leq 10^9$$$), denoting how many ingredients are initially in the $$$i$$$th cabinet.

The next $$$Q$$$ lines will each describe one of Bernardo's action. The $$$i$$$th of these lines will begin with an integer $$$t$$$ ($$$t \in \{1, 2, 3, 4\}$$$), denoting the type of the $$$i$$$th action.

If $$$t = 1$$$, there will also appear a single integer $$$x_i$$$ ($$$1 \leq x_i \leq N$$$), denoting the cabinet to open. If $$$t = 2$$$, there will also appear two integers, $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i, y_i \leq N$$$), denoting the cabinets to swap the ingredients of. If $$$t = 3$$$, there will also appear two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i \leq N$$$, $$$1 \leq y_i \leq 10^9$$$), denoting the cabinet to add $$$y_i$$$ ingredients to. Finally, if $$$t = 4$$$, there will also appear two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i, y_i \leq N$$$), denoting that all ingredients from $$$x_i$$$ should move to cabinet $$$y_i$$$.

Output should consist of $$$Q$$$ lines, the $$$i$$$th of which containing two space-separated integers. The first should represent the length of the longest contiguous subarray of open cabinets after the $$$i$$$th action, and the second should represent the maximum sum of the number of ingredients found within any contiguous subarray of open cabinets.

3 3
1 2 3
1 2
2 1 3
1 3

1 2
1 2
2 3

5 5
1 1 1 1 1
1 2
1 4
1 3
1 1
1 5

1 1
1 1
3 3
4 4
5 5