Description

There are $n$ cars located at positions $a_1, a_2, \ldots, a_n$, and $n$ gas stations located at positions $b_1, b_2, \ldots, b_n$.

Each gas station can serve at most one car, so you must drive the cars to distinct gas stations. The cost for a car to drive from position $x$ to position $y$ is $|x - y|$. Find an assignment that minimizes the sum of costs.

You are also given $q$ operations. In each operation, the position of the $i$-th car is updated to $x$. After each update, you need to output the minimal total cost of an optimal assignment.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$.

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$.

The fourth line contains a positive integer $q$, the number of operations.

Each of the next $q$ lines contains two integers $i$ ($1 \le i \le n$) and $x$, indicating that the position of car $i$ is updated to $x$.

All car and gas station positions are always within $0$ to $10^9$.

Output Format

Output $q + 1$ lines. The first line is the minimal total cost before any operations.

Then output $q$ lines, where the $i$-th line is the minimal total cost after operation $i$.

2
1 2
3 4
1
1 3

4
2

Hint

Sample explanation:

Initially, drive the first car to position $4$ and the second car to position $3$, with a total cost of $|4 - 1| + |3 - 2| = 4$.

After the update, the first car’s position becomes $3$, and the total cost is $|3 - 3| + |4 - 2| = 2$.

For $100\%$ of the testdata, $1 \le n \le 5 \times 10^4$, $0 \le q \le 5 \times 10^4$.

Translated by ChatGPT 5