xxx loves graph theory problems. Recently, xxx's good friends y0rkllu and y0rklld gave xxx a gift—an undirected graph $G=(V,E)$ with no self-loops and no multiple edges, where $n=|V|$ and $m=|E|$. Interestingly, for any subset $V' \subseteq V$ of $7$ vertices, there exist three distinct vertices $p, q \in V'$ and $x \in V - \{p, q\}$ such that $p$ and $q$ are disconnected in the graph after removing vertex $x$.

A graph $G=(V_G, E_G)$ is called $k$-magical if it is connected and for every vertex $p \in V_G$, $\deg_G(p) \le k$. For example, any single vertex is $0$-magical, and any path or cycle is $2$-magical. xxx believes that all $k$-magical graphs are beautiful.

Now, xxx wants to choose a $k$-magical subgraph $G'=(V', E')$ of $G$, where $V' \subseteq V$ and $E' \subseteq E$, to decorate his house. In the graph, each vertex has an aesthetic score $v_p$. Naturally, xxx wants to maximize the sum of the aesthetic scores of all vertices in this subgraph. Furthermore, xxx hates repetition and wants the decoration to be different every day. Therefore, you need to help him find the maximum possible sum of aesthetic scores among all $k$-magical subgraphs of $G$, and the number of distinct $k$-magical subgraphs that achieve this maximum sum. For the latter, you only need to output the count modulo $64123$. Two subgraphs $G_1=(V_1, E_1)$ and $G_2=(V_2, E_2)$ are considered different if and only if $V_1 \ne V_2$ or $E_1 \ne E_2$.

As time passes, xxx may modify the aesthetic scores of certain vertices—for instance, he might get tired of a vertex or start missing one. Therefore, you also need to help him find the answers to the two questions above whenever an aesthetic score changes.

Input

The first line contains three integers $n, m, k$, representing the number of vertices, the number of edges in xxx's simple graph $G$, and the value $k$ for the $k$-magical subgraphs.

The second line contains $n$ integers $v_1, v_2, \dots, v_n$, representing the initial aesthetic score of each vertex.

The next $m$ lines each contain two integers $x_i, y_i \in [1, n]$, representing the $i$-th bidirectional edge connecting vertices $x_i$ and $y_i$.

The next line contains one integer $q$, representing the number of times xxx modifies the aesthetic scores.

The next $q$ lines each contain two integers $p_i, w_i$, representing that in the $i$-th modification, the aesthetic score of vertex $p_i$ is changed to $w_i$.

Output

Output one line of answers initially and after each modification, for a total of $q+1$ lines. Each line should contain two numbers: the maximum aesthetic score sum of a $k$-magical subgraph, and the number of distinct $k$-magical subgraphs that achieve this maximum sum (modulo $64123$).

Examples

Input 1

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

Output 1

6 4
5 5

Note

Initially, there are 4 schemes with the maximum aesthetic score sum of 6:

After xxx changes the aesthetic score of vertex 2 to 1, there are 5 schemes with the maximum aesthetic score sum of 5:

Constraints

For all test cases, $n \ge 2, m, q \ge 0, 2 \le k \le 3, 1 \le v_i, w_i \le 5000$.

The details of each test case are as follows:

Special Property 1: $G$ is guaranteed to be an unrooted tree with $n$ vertices.

Special Property 2: All $v_i, w_i$ are guaranteed to be $1$.

Special Property 3: For any subset $V' \subseteq V$ of $5$ vertices, there exist three distinct vertices $p, q \in V'$ and $x \in V - \{p, q\}$ such that $p$ and $q$ are disconnected in the graph after removing vertex $x$.

For each test case, if the first number in every line is correct but the second number is incorrect in some lines, you can still receive $60\%$ of the points for that test case. (If you do not intend to answer the second question, feel free to output any value for the second number.)