Problem Description

In Plainland, the rich Great Plain River flows across the vast plain. Many years ago, this river was divided among $n$ fishing companies, and each company initially received one continuous river segment. For the $i$-th company (ordered from upstream to downstream), the initial segment length is $a_i$.

Over the years, the fishing companies on the river went through $k$ change events. Each event is one of two types: bankruptcy and split.

Event types:

• Event 1: Bankruptcy
  A company goes bankrupt, and the segment it occupies is transferred to its neighboring companies. If the bankrupt company has only one neighbor, that neighbor takes over the entire segment. If the bankrupt company has two neighbors, the segment is divided into two parts as follows:

  • If the segment length is even, split it evenly into two parts.
  • If the segment length is odd, split it into two parts whose difference is $1$, and the upstream part is smaller.

• Event 2: Split
  A company’s segment splits into two. Suppose the original segment length is $a$, and $a \geq 2$. Then it is split by the following rules:

  • If the segment length is even, split it evenly into two parts.
  • If the segment length is odd, split it into two parts whose difference is $1$, and the upstream part is smaller.

After each bankruptcy or split, the number of companies changes. A bankruptcy event makes one company disappear, and a split event creates two new companies.

Therefore, after each event, every company owns a new river segment.

The Ministry of Finance suggests imposing a tax on fishing companies proportional to the square of the length of the segment they own. To analyze how this tax works, the Minister of Finance wants to know, from the given data, how the sum of squares of all companies’ segment lengths changes after each event.

Task: Write a program that, given the initial segment partition and the subsequent $k$ events, computes the sum of squares of the segment lengths owned by all companies after each event.

Input Format

The first line contains two integers: $n$ and $p$ — the initial number of companies ($2 \leq n \leq 100 000$) and the task number ($0 \leq p \leq 4$).

The second line contains $n$ integers: $a_1, a_2, ..., a_n$, the initial segment lengths owned by each company.

The third line contains an integer $k$ — the number of events ($1 \leq k \leq 100 000$).

The next $k$ lines each describe one event. Each event consists of two integers $e_i$ and $v_i$, where:

• $e_i = 1$ means the $v_i$-th company goes bankrupt.
• $e_i = 2$ means the $v_i$-th company splits.

It is guaranteed that after each event, the company index involved is valid in the current company list.

Output Format

Output $k + 1$ integers. The first integer is the sum of squares of all companies’ segment lengths at the initial moment. Then output one integer per line for the sum after each event.

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

75
105
73
101
83
113

Hint

Explanation of the example

After each event, the segment allocation among companies is shown in the figure below:

Task grading system and subtasks

Subtask 1 (30 points)

$2 \leq n \leq 100$，$1 \leq k \leq 100$，$1 \leq a_i \leq 100$，$p = 1$。

Subtask 2 (30 points)

$2 \leq n \leq 100 000$，$1 \leq k \leq 100 000$，$1 \leq a_i \leq 10^4$，$p = 2$。

Subtask 3 (20 points)

$2 \leq n \leq 100 000$，$1 \leq k \leq 100 000$，$1 \leq a_i \leq 10^4$，$p = 3$。

All event types have $e_i = 1$ (that is, only bankruptcies occur, and there are no splits).

Subtask 4 (20 points)

$2 \leq n \leq 100 000$，$1 \leq k \leq 100 000$，$1 \leq a_i \leq 10^4$，$p = 4$。

Translation source: GPT 5.2.

Translated by ChatGPT 5