Background

JYY, a coder in the JSOI kingdom, has recently become addicted to pay-to-win mobile games. Due to long-term sleep deprivation, his personality has split into the kind JXX and the evil JZZ. JYY's life is at a crossroads, and a game has begun between JXX and JZZ.

Description

There are $N$ major events in JYY's life, numbered $1, 2, \dots, N$. If JXX influences an event, JXX gains a profit of $a_i$. Conversely, if JZZ influences an event, JZZ gains a profit of $b_i$. JXX and JZZ face these $N$ events and take turns choosing an event to influence, starting with JXX. Once an event is chosen, it cannot be chosen again in subsequent turns. The game continues until all events have been influenced by one of the two parties.

The greedy JZZ uses a very simple strategy: in each turn, he chooses the event from the remaining ones that has the largest $b_i$. If there is a tie in $b_i$, he chooses the one with the smallest index.

The kind JXX has a more long-term vision: knowing JZZ's strategy, he adopts an optimal strategy to maximize the difference between his final total profit and JZZ's final total profit.

The initial conditions of the game are given, and JYY wants to know the difference between JXX's final profit and JZZ's final profit. To make the problem more difficult, JXX continuously revises his estimates for each event. JXX provides $Q$ operations, where each operation modifies the $a_i$ value of an event. JYY needs to quickly calculate the result of the game after each operation.

Input

The first line contains a positive integer $N$, representing the number of events. The second line contains $N$ positive integers $a_i$, representing the initial profit JXX gains from influencing each event. The third line contains $N$ positive integers $b_i$, representing the initial profit JZZ gains from influencing each event. The fourth line contains a positive integer $Q$, representing the number of modification operations. The following $Q$ lines each contain two positive integers $x_i$ and $v_i$, representing that the $a_i$ value of the $x_i$-th event is modified to $v_i$.

Output

The first line outputs a positive integer, representing the difference between JXX's and JZZ's profits in the initial state. The following $Q$ lines each output a positive integer, representing the difference between JXX's and JZZ's profits after each modification.

Constraints

• For 20% of the data, $N \le 100$.
• For another 20% of the data, $Q = 0$.
• For 100% of the data, $1 \le N \le 10^5$, $0 \le Q \le 10^5$, $1 \le a_i, b_i, v_i \le 10^9$.

Examples

Input 1

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

Output 1

4
6
6