問題文

$N$ 個の魂がある. 各魂は色を持っており, その色は $1$ 以上 $M$ 以下の整数として表される.

これら $N$ 個の魂から, 以下のようにしてソウルパワーを定める.

$i=1,2, \dots, M$ それぞれに対して, 色 $i$ の魂が $N$ 個中 $x_i$ 個であったとする. このとき, ソウルパワーを $\displaystyle \sum_{i=1}^M x_i^2$ で定める.

最初, $i=1,2, \dots, M$ それぞれに対して, 色 $i$ の魂が $N$ 個中 $A_i$ 個ある.

ここで, これら $N$ 個の魂について, 嘘をついており, 本来なるべき色とは異なる別の色になっている魂があるという情報が $Q$ 個入ってきた.

$q=1,2, \dots, Q$ のそれぞれに対して, $q$ 番目に与えられる情報は $3$ 個の整数の組 $(C_q, K_q, D_q)$ で与えられ, 以下を表している.

• 色 $C_q$ である魂のうち, $K_q$ 個は本当は色 $D_q$ である.

各情報が与えられた際, その情報をもとに魂の色を修正した場合におけるソウルパワーを求めよ.

ただし, 各情報で与えられた色の修正はそれ以降も引き継ぐとする. また, 与えられた情報も嘘が含まれており, 複数回色の修正が発生する魂が存在する可能性もある.

制約

• $1 \leq N \leq 10^9$.
• $2 \leq M \leq 10^5$.
• $0 \leq A_i \leq N \quad (1 \leq i \leq M)$.
• $\displaystyle \sum_{i=1}^M A_i=N$.
• $1 \leq Q \leq 10^5$.
• $1 \leq C_q \leq M \quad (1 \leq q \leq Q)$.
• $q$ 個目の情報が与えられた時点における色 $C_q$ である魂の数を $x_{C_q}$ としたとき, $1 \leq K_q \leq x_{C_q} \quad (1 \leq q \leq Q)$.
• $1 \leq D_q \leq M \quad (1 \leq q \leq Q)$.
• $C_q \neq D_q \quad (1 \leq q \leq Q)$.
• 入力は全て整数である.

入力

$N$ $M$
$A_1$ $A_2$ $\cdots$ $A_M$
$Q$
$C_1$ $K_1$ $D_1$
$C_2$ $K_2$ $D_2$
$\vdots$
$C_Q$ $K_Q$ $D_Q$

出力

出力は $Q$ 行からなる. 第 $q~(1 \leq q \leq Q)$ 行目には $q$ 個目の情報が与えられ, 魂の色の修正を行った後のソウルパワーを整数で出力せよ.

最後に改行を忘れないこと.

サンプル

10 3
2 3 5
2
3 2 1
1 4 2

34
58

7777777 7
1111111 1111111 1111111 1111111 1111111 1111111 1111111
1
3 123456 6

8672456348119