Problem Description

E869120 is an employee at "AtCoder Santa Bureau" and is responsible for optimizing the gift distribution process for Santa every year.

This year, Christmas has arrived as well. His task this year is to gather information about the positions of Santa and houses on "AtCoder Street" and optimize the gift distribution process.

AtCoder Street is a road running from west to east, with a length of $1,000,000,000$ meters. Initially, the information E869120 received about the positions of houses and Santa is as follows:

• There are $N$ houses on that street. The houses are numbered $1, 2, ..., N$, and the house numbered $i$ is located $A_i$ meters from the west end of the road.
• There are $M$ Santas on that street. The Santas are numbered $1, 2, ..., M$, and the Santa numbered $i$ is located $B_i$ meters from the west end of the road.

However, on AtCoder Street, house relocations and Santa movements often occur. Therefore, there will be $Q$ changes in information before Christmas. For the $i$-th change:

• If $T_i = 1$: The position of the house numbered $C_i$ is changed to $D_i$ meters from the west end of the road.
• If $T_i = 2$: The position of the Santa numbered $C_i$ is changed to $D_i$ meters from the west end of the road.

For $i = 0, 1, 2, ..., Q$, answer the following question based on the information immediately after the $i$-th change:

• Determine the total distance that the $M$ Santas need to move to distribute gifts to all houses.
• Note that all Santas always have a sufficient number of gifts.
• Also, Santas can distribute gifts by moving to the position of a house. They cannot throw gifts from a distance. Santas do not need to return to their original positions after distributing all gifts.

Note that "information immediately after the 0-th change" refers to the initial information E869120 received.

Input Format

The input is given from the standard input in the following format:

$N$ $A_1$ $A_2$ $A_3$ ... $A_N$ $M$ $B_1$ $B_2$ $B_3$ ... $B_M$ $Q$ $T_1$ $C_1$ $D_1$ $T_2$ $C_2$ $D_2$ $T_3$ $C_3$ $D_3$ ... $T_Q$ $C_Q$ $D_Q$

Output Format

Output $Q+1$ lines. The $i$-th line should contain the minimum total distance the Santas need to move based on the information immediately after the $(i-1)$-th change.

Sample Input and Output

Sample Input #1

5
12 18 36 50 68
1
25
0

Sample Output #1

69

Sample Input #2

5
138 218 224 110 146
2
127 157
0

Sample Output #2

120

Sample Input #3

10
2412 1276 1948 2000 2542 2558 2070 2712 2820 1542
6
3001 1545 1213 2473 2559 2019
0

Sample Output #3

595

Sample Input #4

10
2412 1276 1948 2000 2542 2558 2070 2712 2820 1542
6
3001 1545 1213 2473 2559 2019
7
1 2 1348
1 8 3200
2 3 2951
1 4 2102
2 5 1137
1 10 420
2 1 2207

Sample Output #4

595
667
866
778
830
959
1676
1840

Notes/Hints

Constraints

• $1 \leq N \leq 100,000$
• $1 \leq M \leq 100,000$
• $0 \leq Q \leq 100,000$
• $0 \leq A_i \leq 1,000,000,000$, $A_i$ is even
• $0 \leq B_i \leq 1,000,000,000$, $B_i$ is odd
• $1 \leq T_i \leq 2$
• When $T_i = 1$, $1 \leq C_i \leq N$, $0 \leq D_i \leq 1,000,000,000$, $D_i$ is even.
• When $T_i = 2$, $1 \leq C_i \leq M$, $0 \leq D_i \leq 1,000,000,000$, $D_i$ is odd.
• There are no changes that result in two houses being at the same position.
• There are no changes that result in two Santas being at the same position.

Partial Points

This problem is divided into several sub-tasks. Your score for a submission will be the sum of the points for the sub-tasks you solved correctly.

1. (2 points) $M = 1$, $Q = 0$.
2. (6 points) $M = 2$, $Q = 0$.
3. (14 points) $N \leq 250$, $M \leq 250$, $Q = 0$.
4. (9 points) $N \leq 3,000$, $M \leq 3,000$, $Q = 0$.
5. (9 points) $Q = 0$.
6. (35 points) $N \leq 40,000$, $M \leq 40,000$, $Q \leq 40,000$, $T_i = 1$.
7. (19 points) $N \leq 40,000$, $M \leq 40,000$, $Q \leq 40,000$.
8. (6 points) No additional constraints.

Sample Explanation 1

The total distance of $69$ is the minimum when the Santa moves as follows:
- Santa $1$ moves to house $1$ and distributes the gift. The distance moved is $13$.
- Santa $1$ moves to house $2$ and distributes the gift. The distance moved is $19$.
- Santa $1$ moves to house $3$ and distributes the gift. The distance moved is $37$.
- Santa $1$ moves to house $4$ and distributes the gift. The distance moved is $51$.
- Santa $1$ moves to house $5$ and distributes the gift. The distance moved is $69$.

Sample Explanation 2

This input example satisfies the constraints of sub-task 2. Note that sub-task 2 does not include cases where $M = 1$ as in Sample Input 1.

Sample Explanation 3

This input example satisfies the constraints of sub-tasks 3, 4, and 5.

见题面 Input 部分

见题面 Output 部分