You have $n$ cars at positions $a_1, a_2, \ldots, a_n$ and $n$ gas stations at positions $b_1, b_2, \ldots, b_n$. Each gas station can only support one car, so you must drive each car to a distinct gas station. The cost of driving a car from position $x$ to position $y$ is $|x-y|$. Determine how to assign the cars to the gas stations to minimize the total cost. Additionally, you have $q$ operations, where each operation updates the position of the $i$-th car to $x$. You must output the minimum total cost after each update.

Input

The first line contains a positive integer $n$.

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

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

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

The next $q$ lines each contain two integers $i$ ($1 \le i \le n$) and $x$, representing the operation of moving the $i$-th car to position $x$.

Output

Output $q+1$ lines. The first line represents the initial minimum cost.

The next $q$ lines each represent the minimum cost after the $i$-th operation.

Examples

Input 1

2
1 2
3 4
1
1 3

Output 1

4
2

Note 1

Initially, drive the first car to position $4$ and the second car to position $3$. The cost is $|4-1|+|3-2|=4$.

After the modification, the first car's position becomes $3$. The cost is $|3-3|+|4-2|=2$.

Subtasks

For $100\%$ of the data, $1 \le n, q \le 5 \times 10^4$, and all car and gas station positions are between $0$ and $10^9$.