River

The Big Flat river, rich in fish, flows through Flatland. Many years ago the river was divided among n fishing companies, each receiving a contiguous segment of the river. Numbered in order from the source, the i-th company initially received a segment of length ai.

Since then k events have occurred with the fishing companies of Flatland. Each event was of one of two types: the bankruptcy of a company or the split of a company into two.

In some events the river segment owned by the company involved is divided into two parts. Every such segment has length at least 2. The division follows this rule. If the segment has even length, it is divided into two equal parts. Otherwise it is divided into two parts whose lengths differ by exactly one, and the part closer to the river's source is the shorter one.

When a company goes bankrupt, the following happens. The river segment that belonged to the bankrupt company passes to its neighbors. If the bankrupt company has one neighbor, that neighbor receives the entire segment of the bankrupt company. If there are two neighbors, the segment is divided into two parts in the manner described above, after which each neighbor appends the part nearest to it to its own segment.

When a company splits, the river segment that belonged to it is always divided into two parts in the manner described above. The split company is liquidated, and two new companies are formed.

Thus after each event every company owns some segment of the river.

The Ministry of Finance of Flatland proposes to introduce a tax on fishing companies proportional to the square of the length of the river segment owned by the company. To analyze how this tax would work, the minister wants to use the available data to find out how the value equal to the sum of squares of the lengths of the river segments owned by the companies changed after each event that occurred.

You must write a program that, given the initial division of the river among the companies and the list of events that occurred with the companies, determines the sum of squares of the lengths of the river segments owned by the companies at the initial moment and after each event.

The first line of the input file contains two integers: n and p, the initial number of companies (2 ≤ n ≤ 100 000) and the subtask number (0 ≤ p ≤ 4).

The second line of the input file contains n integers a1, a2, …, an, the lengths of the initial segments of the river.

The third line of the input file contains an integer k, the number of events that occurred with the companies (1 ≤ k ≤ 100 000).

The following k lines contain descriptions of the events. The i-th line contains two integers: ei and vi, the type of the event and the number of the company involved. The value ei = 1 means that the company which, after all previous events, is the vi-th in order counting from one from the river's source, has gone bankrupt, and the value ei = 2 means that this company has split into two.

It is guaranteed that vi does not exceed the current number of companies. It is guaranteed that if the segment of a company must be divided into two parts on bankruptcy or split, it has length at least 2. It is guaranteed that if only one company remains on the river, it does not go bankrupt.

The output file must contain (k + 1) integers, one per line. The first line must contain the initial sum of squares of the lengths of the river segments, and each of the following k lines must contain the sum of squares of the lengths of the river segments after the next event.

The distribution of river segments among the companies after each event described in the example is shown in the figures below.

After the bankruptcy of company 1

After the split of company 1

After the bankruptcy of company 3

After the split of company 2

After the bankruptcy of company 3