Problem Statement

You are given an integer sequence $A=(A_1,A_2,\ldots,A_N)$ of length $N$ and an integer sequence $B=(B_1,B_2,\ldots,B_M)$ of length $M$. Here, $N$ is even.

You are given $Q$ queries. The $q$-th query is given as a triple of integers $(t_q,i_q,x_q)$, and it does the following.

• If $t_q=1$: In this case, $1\leq i_q\leq N$. This query changes $A_{i_q}$ to $x_q$.
• If $t_q=2$: In this case, $1\leq i_q\leq M$. This query changes $B_{i_q}$ to $x_q$.

After processing each query, find the answer to the following subproblem.

Initialize a multiset $X$ with $X=\lbrace A_1,A_2,\ldots,A_N\rbrace$. For $j=1,2,\ldots,M$, perform the following operation:

• Insert $B_j$ into $X$. Then, remove one median of $X$ from $X$.

Find the sum of elements in $X$ when all operations are finished.

What is a median? When $N$ is even, the median of a multiset $X$ with $N+1$ elements is the $\left(1+\frac{N}{2}\right)$-th value in ascending order among the elements of $X$. For example, the median of $X=\lbrace 1, 3, 4, 5, 8\rbrace$ is $4$, and the median of $X=\lbrace 2,2,2\rbrace$ is $2$. Note that in this problem, the multiset for which we consider the median always has an odd number of elements.

Constraints

• $1\leq N,M,Q\leq 2\times 10^5$
• $N$ is even.
• $1\leq A_i\leq 10^9$
• $1\leq B_i\leq 10^9$
• $t_q\in\lbrace 1,2\rbrace$
• If $t_q=1$, then $1\leq i_q\leq N$
• If $t_q=2$, then $1\leq i_q\leq M$
• $1\leq x_q\leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M Q
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_M
t_1 i_1 x_1
\vdots
t_Q i_Q x_Q

Output

Output $Q$ lines. The $q$-th line should contain the answer to the subproblem immediately after processing the $q$-th query.