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$ 的余数）”这两个问题的答案。

样例输入

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

样例输出

6 4
5 5

样例说明

在最开始，存在以下 $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\%$ 的分数。（如果你不打算回答第二个问题，请随意输出第二个数）