xxx 很喜歡圖論問題。最近，xxx 的好朋友 y0rkllu 和 y0rklld 送給 xxx 一份禮物——一張無自環、無重邊的無向圖 $G=(V,E)$，其中 $n=|V|,m=|E|$。有趣的是，任取 $V$ 中的 $7$ 個點構成集合 $V'$，都存在三個不同的點 $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$-神奇的。例如，任意一個單點都是 $0$-神奇的，任意一個鏈或環都是 $2$-神奇的。xxx 認為所有的 $k$-神奇的圖都是很漂亮的。

現在 xxx 想要取圖 $G$ 的一個 $k$-神奇的子圖 $G'=(V',E'),V'\subseteq V,E'\subseteq E$，作為房子的裝飾品。在圖中，xxx 對每個節點都有一個美觀評分 $v_p$——xxx 自然希望這張子圖中，所有點的美觀評分的和最大。並且 xxx 討厭重複，他希望每天的裝飾都能不同。因此 xxx 希望你幫他求出圖 $G$ 的所有 $k$-神奇子圖中，美觀評分和最大的那個子圖的美觀評分和是多少，以及有多少不同的 $k$-神奇子圖的美觀評分和達到最大值。對於後一個問題，xxx 只需要知道不同的子圖個數除以 $64123$ 的餘數即可。兩張子圖 $G_1=(V_1,E_1),G_2=(V_2,E_2)$ 不同，當且僅當 $V_1\ne V_2$ 或 $E_1\ne E_2$。

隨著時間的變動，xxx 可能會修改某些節點的美觀評分——比如某個節點看膩了，或想念某個節點了。因此，你還需要幫助他在每次美觀評分發生變化的時候，都求出上述兩個問題的答案。

輸入格式

第一行包含 $3$ 個整數 $n,m,k$，表示 xxx 的簡單圖 $G$ 的邊數、點數及 xxx 喜歡的 $k$-神奇子圖的 $k$ 值；

第二行包含 $n$ 個整數 $v_1, v_2,…,v_n$，表示每個節點初始情況下的美觀評分；

接下來 $m$ 行，其中第 $i$ 行包含 $2$ 個整數 $x_i,y_i\in [1,n]$，表示圖中的第 $i$ 條雙向邊連接節點 $x_i$ 和節點 $y_i$；

接下來一行包含 $1$ 個整數 $q$，表示 xxx 修改美觀評分的次數；

接下來 $q$ 行，其中第 $i$ 行包含兩個整數 $p_i,w_i$，表示 xxx 在第 $i$ 次修改中，將節點 $p_i$ 的美觀評分修改為了 $w_i$。

輸出格式

在剛開始及每次修改過後輸出 $1$ 行答案，因此總共應該輸出 $q+1$ 行；輸出的每一行包含兩個數，分別表示「美觀評分和最大的那個子圖的美觀程度是多少」和「有多少不同的 $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

說明 1

在最開始，存在以下 $4$ 種美觀評分之和為最大值 $6$ 的方案：

當 xxx 修改節點 $2$ 的美觀程度為 $1$ 後，存在以下 $5$ 種美觀評分之和為最大值 $5$ 的方案：

資料範圍與約定

對於所有資料，保證 $n\ge 2,m,q\ge 0,2\le k\le 3,1\le v_i,w_i\le 5000$。

每個測試點的詳細資訊如下表：

特殊性質 1：保證 $G$ 是一棵 $n$ 個節點的無根樹。

特殊性質 2：保證所有的 $v_i,w_i$ 均為 $1$。

特殊性質 3：任取 $V$ 中的 $5$ 個點構成集合 $V'$，都存在三個不同的點 $p,q\in V',x\in V-\{p,q\}$，使得從圖中刪去點 $x$ 後，$p$ 和 $q$ 不連通。

對於每個測試點，如果你每行的第一個數都是對的，但某些行的第二個數出錯了，你仍然可以獲得該測試點 $60\%$ 的分數。（如果你不打算回答第二個問題，請隨意輸出第二個數）