Description

小七在施展完變身魔法後,與她的好朋友小皮一起去爬山。
小皮與小七都是登山愛好者,兩人曾經爬過大大小小的山,今天因為兩人相距太遠了,所以他們決定同時爬不同的山,小皮爬 A 山,小七則爬 B 山。

A 山共有 $n$ 個階梯,第 $i$($1\leq i\leq n$)階的海拔為 $a_i$ 公尺,並且海拔是嚴格遞增的,也就是 $a_i<a_{i+1}$($1\leq i<n$)。
B 山共有 $m$ 個階梯,第 $j$($1\leq j\leq m$)階的海拔為 $b_j$ 公尺,並且海拔也是嚴格遞增的,也就是 $b_j<b_{j+1}$($1\leq j<m$)。

兩人在時刻 $t=1$ 時都在所處山脈的第 $1$ 階,小皮的目標是爬到 A 山的第 $n$ 階,小七則想要爬到 B 山的第 $m$ 階。
為了有同時爬山的感覺,兩人邊爬山時會邊通話,從 $t=1$ 開始,每經過一個時刻,兩人會做以下的事情:

  • 若小皮還沒到達 A 山的第 $n$ 階,小七也還沒到達 B 山的第 $m$ 階,那兩人可以決定讓其中一人移動到下一階,也就是讓小皮從第 $i$ 階移動到第 $i+1$ 階,或是讓小七從第 $j$ 階移動到第 $j+1$ 階,另外一人則留在原本的階梯。
  • 若其中一人已經到達山脈的最後一階了,則讓另外一人移動到下一階:例如當小七已經在 B 山的第 $m$ 階了,那就讓小皮從第 $i$ 階移動到第 $i+1$ 階。

當 $t=n+m-1$ 時,小皮會在 A 山的第 $n$ 階,小七會在 B 山的第 $m$ 階,兩人此時不再移動。

經過上述兩人一連串的決定後,小皮在時刻 $t$($1\leq t\leq n+m-1$)會位於 A 山的第 $p_t$ 階,小七則會位於 B 山的第 $q_t$ 階。
兩人在同一時刻的海拔差距越大,違和感就會越大,違和感的計算方式為兩人海拔差距的平方值,在時刻 $t$ 的違和感可以表示成 $(a_{p_t}-b_{q_t})^ 2$。

兩人的目標是讓 $n+m-1$ 個時刻的總違和感最小,也就是 $\sum\limits_{t=1}^ {n+m-1}(a_{p_t}-b_{q_t})^ 2$ 最小。

令人驚訝的是,地殼的變動可能會影響階梯的高度,依序有 $k$ 個地殼變動發生,每個地殼變動的形式可能為 $1\ x\ h$ 或 $2\ y\ h$。

  • 若形式為 $1\ x\ h$,代表這次的地殼變動會讓 A 山第 $x$ 個階梯的海拔變成 $h$,也就是使 $a_x$ 變成 $h$。
  • 若形式為 $2\ y\ h$,代表這次的地殼變動會讓 B 山第 $y$ 個階梯的海拔變成 $h$,也就是使 $b_y$ 變成 $h$。
  • 地殼變動的影響是永久的,也就是說當 $a_x$ 或 $b_y$ 變成 $h$ 後,除非之後的地殼變動影響到同一個階梯,否則此階梯的海拔會維持在 $h$。
  • 每次地殼變動完,A 山、B 山階梯的海拔仍然保持嚴格遞增,也就是維持 $a_i<a_{i+1}$($1\leq i<n$)與 $b_j<b_{j+1}$($1\leq j<m$)。(不然就不叫爬山了)

請你在每次地殼變動完,輸出小皮與小七在經過一連串的決定爬到最後一階後,總違和感 $\sum\limits_{t=1}^ {n+m-1}(a_{p_t}-b_{q_t})^ 2$ 最小可以是多少。

Input Format

第一行有三個正整數 $n,m,k$,分別代表 A 山階梯數、B 山階梯數、地殼變動發生幾次。
第二行有 $n$ 個嚴格遞增的正整數 $a_1\sim a_n$,代表 A 山階梯的海拔。
第三行有 $m$ 個嚴格遞增的正整數 $b_1\sim b_m$,代表 B 山階梯的海拔。

接下來 $k$ 行,每行輸入的三個正整數形式可能為 $1\ x\ h$ 或 $2\ y\ h$,代表此次地殼變動將 A 山第 $x$ 階或 B 山第 $y$ 階的海拔變成 $h$ 了。

對於所有測試資料:

  • $2\leq n,m\leq 3\times 10^ 5$
  • $1\leq k\leq 10^ 5$
  • $1\leq a_i,b_j\leq 2\times 10^ 6$($1\leq i\leq n,1\leq j\leq m$)
  • $a_i<a_{i+1}$($1\leq i<n$)
  • $b_j<b_{j+1}$($1\leq j<m$)
  • $1\leq x\leq n,1\leq y\leq m$
  • $1\leq h\leq 2\times 10^ 6$
  • 保證每次地殼變動完 $a,b$ 陣列皆保持嚴格遞增

Output Format

每次地殼變動完,輸出一整數,代表小皮與小七在經過一連串的決定爬到最後一階後,總違和感 $\sum\limits_{t=1}^ {n+m-1}(a_{p_t}-b_{q_t})^ 2$ 最小可以是多少。

Sample Input 1

2 2 2
5 6
1 4
2 2 7
1 1 1

Sample Output 1

21
26

Sample Input 2

4 9 5
7 8 12 20
1 5 8 14 15 18 20 23 24
2 2 3
2 8 22
1 2 11
1 4 18
1 1 10

Sample Output 2

136
131
133
149
230

Hints

在範例測資一,初始 $a=[5,6],b=[1,4]$。

經過第 $1$ 次的地殼變動,$a=[5,6],b=[1,7]$,此時 $p=[1,1,2],q=[1,2,2]$,
會有最小的總違和感: $\sum\limits_{t=1}^ {n+m-1}(a_{p_t}-b_{q_t})^ 2=(a_1-b_1)^ 2+(a_1-b_2)^ 2+(a_2-b_2)^ 2=4^ 2+(-2)^ 2+(-1) ^ 2=21$

經過第 $2$ 次的地殼變動,$a=[1,6],b=[1,7]$,此時 $p=[1,2,2],q=[1,1,2]$,
會有最小的總違和感: $\sum\limits_{t=1}^ {n+m-1}(a_{p_t}-b_{q_t})^ 2=(a_1-b_1)^ 2+(a_2-b_1)^ 2+(a_2-b_2)^ 2=0^ 2+5^ 2+(-1) ^ 2=26$

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~4 $n,m,k\leq 10$ 12
3 0~10 $n,m,k\leq 400$ 11
4 0~16 $n,m,k\leq 5000$ 26
5 0, 2, 17~20 $n=2$ 15
6 21~34, 55~56 地殼變動形式只會是 $1\ x\ h$ 17
7 0~58 無其他限制 19

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 65536 1 2 3 4 5 7
1 3000 262144 65536 1 2 3 4 7
2 3000 262144 65536 2 3 4 5 7
3 3000 262144 65536 2 3 4 7
4 3000 262144 65536 2 3 4 7
5 3000 262144 65536 3 4 7
6 3000 262144 65536 3 4 7
7 3000 262144 65536 3 4 7
8 3000 262144 65536 3 4 7
9 3000 262144 65536 3 4 7
10 3000 262144 65536 3 4 7
11 3000 262144 65536 4 7
12 3000 262144 65536 4 7
13 3000 262144 65536 4 7
14 3000 262144 65536 4 7
15 3000 262144 65536 4 7
16 3000 262144 65536 4 7
17 3000 262144 65536 5 7
18 3000 262144 65536 5 7
19 3000 262144 65536 5 7
20 3000 262144 65536 5 7
21 3000 262144 65536 6 7
22 3000 262144 65536 6 7
23 3000 262144 65536 6 7
24 3000 262144 65536 6 7
25 3000 262144 65536 6 7
26 3000 262144 65536 6 7
27 3000 262144 65536 6 7
28 3000 262144 65536 6 7
29 3000 262144 65536 6 7
30 3000 262144 65536 6 7
31 3000 262144 65536 6 7
32 3000 262144 65536 6 7
33 3000 262144 65536 6 7
34 3000 262144 65536 6 7
35 3000 262144 65536 7
36 3000 262144 65536 7
37 3000 262144 65536 7
38 3000 262144 65536 7
39 3000 262144 65536 7
40 3000 262144 65536 7
41 3000 262144 65536 7
42 3000 262144 65536 7
43 3000 262144 65536 7
44 3000 262144 65536 7
45 3000 262144 65536 7
46 3000 262144 65536 7
47 3000 262144 65536 7
48 3000 262144 65536 7
49 3000 262144 65536 7
50 3000 262144 65536 7
51 3000 262144 65536 7
52 3000 262144 65536 7
53 3000 262144 65536 7
54 3000 262144 65536 7
55 3000 262144 65536 6 7
56 3000 262144 65536 6 7
57 3000 262144 65536 7
58 3000 262144 65536 7