xxx はグラフ理論の問題が大好きです。最近、xxx の親友である y0rkllu と y0rklld は、xxx にプレゼントとして無向グラフ $G=(V,E)$ を贈りました。このグラフには自己ループも多重辺もありません。ここで $n=|V|, m=|E|$ です。興味深いことに、$V$ から任意の $7$ 個の点を選んで集合 $V'$ を作ると、必ず $3$ つの異なる点 $p, q \in V', x \in V-\{p,q\}$ が存在し、グラフから点 $x$ を削除すると $p$ と $q$ が非連結になります。
グラフ $G=(V_G, E_G)$ が連結であり、かつ任意のノード $p \in V_G$ に対して $\deg_G(p) \le k$ が成り立つとき、xxx はそのグラフ $G$ を $k$-神奇（$k$-magical）と呼びます。例えば、任意の単一ノードは $0$-神奇であり、任意のパスやサイクルは $2$-神奇です。xxx はすべての $k$-神奇なグラフは美しいと考えています。
今、xxx はグラフ $G$ の $k$-神奇な部分グラフ $G'=(V', E'), V' \subseteq V, E' \subseteq E$ を家の装飾として手に入れたいと考えています。グラフ内の各ノードには美観スコア $v_p$ が設定されており、xxx は当然、この部分グラフに含まれるすべてのノードの美観スコアの合計が最大になることを望んでいます。また、彼は重複を嫌うため、毎日異なる装飾をしたいと考えています。そのため、グラフ $G$ のすべての $k$-神奇な部分グラフの中で、美観スコアの合計が最大となる部分グラフの美観スコアの合計と、その最大値に達する異なる $k$-神奇な部分グラフの個数を求めてください。後者の問題については、異なる部分グラフの個数を $64123$ で割った余りを求めてください。2 つの部分グラフ $G_1=(V_1, E_1), G_2=(V_2, E_2)$ が異なるとは、$V_1 \ne V_2$ または $E_1 \ne E_2$ であることを指します。
時間の経過とともに、xxx は特定のノードの美観スコアを変更することがあります。例えば、あるノードに飽きたり、あるいはあるノードを懐かしく思ったりするためです。したがって、美観スコアが変化するたびに、上記 2 つの問題の答えを求める手助けをしてください。
入力
入力の最初の行には、$3$ つの整数 $n, m, k$ が含まれており、それぞれ xxx の単純グラフ $G$ の頂点数、辺数、および xxx が好む $k$-神奇部分グラフの $k$ の値を表します。
次の行には $n$ 個の整数 $v_1, v_2, \dots, v_n$ が含まれており、各ノードの初期美観スコアを表します。
続く $m$ 行の各行には、$2$ つの整数 $x_i, y_i \in [1, n]$ が含まれており、グラフの $i$ 番目の双方向辺がノード $x_i$ とノード $y_i$ を結んでいることを表します。
次の行には $1$ つの整数 $q$ が含まれており、xxx が美観スコアを変更する回数を表します。
続く $q$ 行の各行には、$2$ つの整数 $p_i, w_i$ が含まれており、xxx が $i$ 回目の変更でノード $p_i$ の美観スコアを $w_i$ に変更することを表します。
出力
最初および各変更の後に $1$ 行ずつ答えを出力してください。したがって、合計で $q+1$ 行出力することになります。各行には $2$ つの数値をスペース区切りで出力してください。それぞれ「美観スコアの合計が最大となる部分グラフの美観スコアの合計」と「最大値に達する異なる $k$-神奇部分グラフの個数（$64123$ で割った余り）」です。
入出力例
入力 1
5 5 2 1 2 1 2 2 2 3 2 1 1 4 1 3 1 5 1 2 1
出力 1
6 4 5 5
注記
最初、美観スコアの合計が最大値 $6$ となる方案は以下の $4$ 通り存在します。
| 编号 | $V’$ | $E’$ |
|---|---|---|
| 1 | $\{1,2,3,4\}$ | $\{(2,3),(1,2),(1,4)\}$ |
| 2 | $\{1,2,3,4\}$ | $\{(2,3),(1,3),(1,4)\}$ |
| 3 | $\{1,2,3,5\}$ | $\{(2,3),(1,2),(1,5)\}$ |
| 4 | $\{1,2,3,5\}$ | $\{(2,3),(1,3),(1,5)\}$ |
xxx がノード $2$ の美観スコアを $1$ に変更した後、美観スコアの合計が最大値 $5$ となる方案は以下の $5$ 通り存在します。
| 编号 | $V'$ | $E'$ |
|---|---|---|
| 1 | $\{1,2,3,4\}$ | $\{(2,3),(1,2),(1,4)\}$ |
| 2 | $\{1,2,3,4\}$ | $\{(2,3),(1,3),(1,4)\}$ |
| 3 | $\{1,2,3,5\}$ | $\{(2,3),(1,2),(1,5)\}$ |
| 4 | $\{1,2,3,5\}$ | $\{(2,3),(1,3),(1,5)\}$ |
| 5 | $\{1,4,5\}$ | $\{(1,4),(1,5)\}$ |
制約
すべてのデータにおいて、$n \ge 2, m, q \ge 0, 2 \le k \le 3, 1 \le v_i, w_i \le 5000$ を満たします。
各テストケースの詳細は以下の表の通りです。
| 子課題 | 総得点 | テストケース | $n$ | $m$ | $k$ | $q$ | 特殊性質 |
|---|---|---|---|---|---|---|---|
| 1 | 7 | 1 | $\le 10$ | $\le 20$ | $= 3$ | $\le 100$ | 無 |
| 2 | 18 | 2,3 | $\le 10000$ | $=n-1$ | $=2$ | $\le 1000$ | 1 |
| 3 | 7 | 4,5 | $\le 50000$ | $=n-1$ | $=2$ | $\le 50000$ | 1 |
| 4 | 15 | 6,7,8 | $\le 100000$ | $=n-1$ | $=2$ | $\le 200000$ | 1 |
| 5 | 12 | 9,10 | $\le 100$ | $\le 300$ | $= 2$ | $=0$ | 2,3 |
| 6 | 9 | 11,12 | $\le 1000$ | $\le 3000$ | $= 3$ | $=0$ | 3 |
| 7 | 5 | 13 | $\le 30000$ | $\le 100000$ | $= 3$ | $=0$ | 無 |
| 8 | 14 | 14,15 | $\le 100000$ | $\le 300000$ | $= 3$ | $=0$ | 無 |
| 9 | 3 | 16 | $\le 30000$ | $\le 55000$ | $=3$ | $\le 10000$ | 無 |
| 10 | 10 | 17~20 | $\le 30000$ | $\le 100000$ | $=3$ | $\le 10000$ | 無 |
特殊性質 1：$G$ は $n$ 個のノードを持つ無根木であることが保証される。
特殊性質 2：すべての $v_i, w_i$ が $1$ であることが保証される。
特殊性質 3：$V$ から任意の $5$ 個の点を選んで集合 $V'$ を作ると、必ず $3$ つの異なる点 $p, q \in V', x \in V-\{p,q\}$ が存在し、グラフから点 $x$ を削除すると $p$ と $q$ が非連結になる。
各テストケースにおいて、各行の最初の数値が正しく、2 番目の数値が間違っている場合でも、そのテストケースの $60\%$ のスコアを獲得できます。（2 番目の問題に回答するつもりがなければ、適当な数値を出力してください。）