Joint Training

With a special training period approaching, $N$ units work together in a joint training exercise. Each joint training session selects a total of $2N$ soldiers. No unit has a limit on how many soldiers it can send, and some units may send none. Each participating unit rents a bus to carry its soldiers to the training site. The rental cost for unit $i$ is $a_i$. The cost of a joint training session is the sum of the bus rental costs of the participating units.

The session is held with the $2N$ soldiers standing in a line. After training ends, for every pair of adjacent soldiers, the dissatisfaction between their units increases by $1$. Pairs from the same unit do not increase dissatisfaction. The commander does not approve any plan in which two adjacent soldiers come from units with dissatisfaction at least $K$. Before training starts, the dissatisfaction between every pair of units is $0$.

During the special training period, the commander must write reports on three kinds of events.

1. The commander receives a training plan that lists the units of the $2N$ soldiers in line order. If any pair of adjacent soldiers has dissatisfaction at least $K$, the plan is not approved. Otherwise, the training is carried out and the commander reports its total cost.
2. A dispute breaks out between units $s_i$ and $t_i$, and the dissatisfaction between the two units increases by $x_i$. To find a budget that allows training under any circumstances, the commander reports the maximum cost among all feasible plans.
3. Due to rising prices, the bus rental cost of unit $s_i$ increases by $x_i$. Paying each unit a different amount makes administration complicated, so the commander reports the maximum number of distinct costs among the training plans that include unit $s_i$.

The increases in dissatisfaction and cost from each event accumulate and remain in effect until all events end.

The first line contains two integers $N$ and $K$, the number of units and the smallest dissatisfaction value that forbids adjacency.

The second line contains the bus rental costs $a_i$ of each unit, separated by spaces.

The third line contains the number of events $Q$.

The next $Q$ lines each give the event type $q_i$ and the parameters for that event.

• If $q_i=1$, the unit numbers $b_i$ of the soldiers are given in line order, separated by spaces.
• If $q_i=2$, the two unit numbers $s_i$ and $t_i$ and the increase in dissatisfaction $x_i$ are given, separated by spaces.
• If $q_i=3$, the unit number $s_i$ and the increase in bus rental cost $x_i$ are given, separated by spaces.

On the $i$-th line, print the answer to the $i$-th event.

• If $q_i=1$, print the total cost of the training. If the plan is not approved, print -1.
• If $q_i=2$, print the maximum cost of a training session that can be carried out.
• If $q_i=3$, print the maximum number of distinct costs among the training plans that include unit $s_i$.

• $1 \leq N \leq 100\,000$; $1 \leq K \leq 10^9$
• $1 \leq a_i \leq 10^9$
• $1 \leq Q \leq 100\,000$
• $1 \leq q_i \leq 3$
• $1 \leq b_i, s_i, t_i \leq N$
• $s_i \neq t_i$
• $1 \leq x_i \leq 10^9$
• The total number of integers in the input does not exceed $500\,000$.