While learning algorithms, Xiao Bo grasped the most classic greedy problem: the Fruit Merging problem.

This problem provides $n$ fruits, where the $i$-th fruit has a weight of $a_i$. Each fruit merging operation allows you to choose any two fruits to merge. Assuming the weights of these two fruits are $a_i$ and $a_j$, the cost of this merge is the sum of the weights of the two fruits, $a_i + a_j$. After merging, these two fruits disappear and are replaced by a single fruit with weight $a_i + a_j$. The goal of this problem is to find the minimum total cost to merge $n$ fruits into one through $n-1$ operations.

Xiao Bo thought this problem was too simple, so he began to ponder the dynamic version of this problem: initially, a multiset of fruit weights $A = \{a_1, a_2, \dots, a_n\}$ is given, followed by $m$ operations, where each operation is one of the following two types:

1. Add a fruit with weight $x$ to the multiset $A$.
2. Remove a fruit with weight $x$ from the multiset $A$ (it is guaranteed that a fruit with weight $x$ exists in $A$).

After each operation, Xiao Bo wants to quickly solve the fruit merging problem for the current multiset $A$.

Unfortunately, he could not think of an efficient algorithm after a long time. At this point, his friend Xiao Si came to help him. Xiao Si provided a set $B$ of "54 binary good fruits", $B = \{2, 4, 8, 16, 32, \dots, 2^{54}\}$. Formally, the elements in set $B$ are $2^k$ for $1 \le k \le 54$, totaling 54 integers.

Xiao Si suggested that as long as these good fruits from set $B$ are fixedly added, Xiao Bo's dynamic problem can be solved, and he left this difficult problem to Xiao Bo.

Now, please help Xiao Bo solve the following problem:

Given a multiset $A$ of size $n$, representing the weights of $n$ fruits; given $m$ operations, with the forms described above; after each operation, find the answer to the fruit merging problem for the multiset $A \cup B$ (i.e., consider the fruits in the current multiset $A$ and the fruits in set $B$ simultaneously, and then find the minimum total cost to merge them all into one fruit).

Input

The first line contains two positive integers $n, m$ ($1 \le n \le 10^5, 1 \le m \le 2 \times 10^5$), representing the initial size of set $A$ and the number of subsequent operations, respectively.

The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), representing the initial weights of the fruits in set $A$.

The next $m$ lines each first input two integers $op, x$ ($op \in \{1, 2\}, 1 \le x \le 10^9$).

If $op = 1$, it means inserting a fruit with weight $x$ into the multiset $A$.

If $op = 2$, it means removing a fruit with weight $x$ from the multiset $A$ (it is guaranteed that the object to be removed exists).

Note that set $B$ is a fixed set given in the problem, so it does not need to be input.

Output

Output $m$ lines in total. After each operation, output one line containing an integer representing the minimum total cost of the fruit merging problem for the current multiset $A \cup B$.

Examples

Input 1

1 2
1
2 1
1 2

Output 1

72057594037927822
72057594037927932

Input 2

6 10
1 1 4 5 1 4
1 9
1 9
2 1
2 1
2 4
2 5
2 1
2 4
2 9
2 9

Output 2

72057594037929188
72057594037929672
72057594037929615
72057594037929558
72057594037929338
72057594037929065
72057594037929008
72057594037928788
72057594037928304
72057594037927822