Jumping Choreography

A group of frogs performs a line dance. Each frog stands on an integer coordinate, and the dance is a sequence of jumps. The $j$-th jump a frog makes has length exactly $j$, and the frog picks its direction, left or right, freely. So the first jump has length 1, the second has length 2, and the third has length 3. Nothing restricts the coordinates a jump passes over or lands on, so a frog may visit negative coordinates, and several frogs may stand on the same coordinate.

The dance ends with every frog gathered at the tower position $t$, where the frogs stack up. Each frog jumps on its own, and a frog that already stands on $t$ does not have to jump at all. The cost of the choreography is the total number of jumps made by all frogs, and that total has to be as small as possible.

The king comes to the rehearsal every day and makes one change. He adds a frog, removes a frog, or moves the tower. After each change is applied, report the smallest possible total number of jumps at that moment.

The first line has the number of frogs $n$ and the initial tower position $t$ ($0 \le n \le 5000$, $0 \le t \le 10^6$).

The second line has the starting positions $p_1, \dots, p_n$ of the frogs ($0 \le p_i \le 10^6$). This line is empty when $n = 0$.

The third line has the number of changes $C$ ($0 \le C \le 10^6$).

Each of the next $C$ lines holds one change, in one of these three forms ($0 \le a \le 10^6$).

• + a adds a frog at position $a$.
• - a removes one frog that started at position $a$. At least one frog started at position $a$ when this change is given.
• t a moves the tower to position $a$.

The king adds or removes a frog at most 5000 times in total.

Apply the $C$ changes in order. After each change, print the smallest possible total number of jumps on its own line.