xxx uwielbia problemy z teorii grafów. Niedawno jego przyjaciele, y0rkllu i y0rklld, podarowali mu prezent – graf nieskierowany $G=(V,E)$ bez pętli własnych i krawędzi wielokrotnych, gdzie $n=|V|, m=|E|$. Co ciekawe, dla dowolnego zbioru $V'$ składającego się z $7$ wierzchołków z $V$, istnieją trzy różne wierzchołki $p, q \in V'$ oraz $x \in V-\{p, q\}$ takie, że po usunięciu wierzchołka $x$ z grafu, $p$ i $q$ stają się niespójne.
Jeśli graf $G=(V_G, E_G)$ jest spójny oraz dla każdego wierzchołka $p \in V_G$ zachodzi $\deg_G(p) \le k$, xxx nazywa graf $G$ $k$-magicznym. Na przykład, każdy pojedynczy wierzchołek jest $0$-magiczny, a każda ścieżka lub cykl jest $2$-magiczny. xxx uważa, że wszystkie $k$-magiczne grafy są bardzo piękne.
Teraz xxx chce wybrać $k$-magiczny podgraf $G'=(V', E')$ grafu $G$, gdzie $V' \subseteq V$ oraz $E' \subseteq E$, jako dekorację swojego domu. W grafie każdy wierzchołek ma ocenę estetyczną $v_p$. xxx naturalnie pragnie, aby suma ocen estetycznych wszystkich wierzchołków w tym podgrafie była jak największa. Ponadto xxx nie lubi powtórzeń i chce, aby dekoracja każdego dnia była inna. Dlatego prosi Cię o obliczenie, jaka jest maksymalna suma ocen estetycznych wśród wszystkich $k$-magicznych podgrafów grafu $G$, oraz ile istnieje różnych $k$-magicznych podgrafów, których suma ocen estetycznych osiąga tę wartość maksymalną. W przypadku drugiego pytania, xxx potrzebuje jedynie znać liczbę różnych podgrafów modulo $64123$. Dwa podgrafy $G_1=(V_1, E_1)$ oraz $G_2=(V_2, E_2)$ są różne wtedy i tylko wtedy, gdy $V_1 \ne V_2$ lub $E_1 \ne E_2$.
Wraz z upływem czasu xxx może modyfikować oceny estetyczne niektórych wierzchołków – na przykład, gdy znudzi mu się dany wierzchołek lub zatęskni za innym. Dlatego musisz również pomóc mu w obliczeniu odpowiedzi na powyższe dwa pytania za każdym razem, gdy ocena estetyczna ulegnie zmianie.
Wejście
Pierwsza linia zawiera $3$ liczby całkowite $n, m, k$, oznaczające liczbę wierzchołków, liczbę krawędzi grafu $G$ oraz wartość $k$ dla $k$-magicznych podgrafów, które lubi xxx.
Druga linia zawiera $n$ liczb całkowitych $v_1, v_2, \dots, v_n$, oznaczających początkowe oceny estetyczne każdego wierzchołka.
Następne $m$ linii zawiera po $2$ liczby całkowite $x_i, y_i \in [1, n]$, oznaczające $i$-tą krawędź dwukierunkową łączącą wierzchołki $x_i$ oraz $y_i$.
Kolejna linia zawiera $1$ liczbę całkowitą $q$, oznaczającą liczbę modyfikacji ocen estetycznych.
Następne $q$ linii zawiera po dwie liczby całkowite $p_i, w_i$, oznaczające, że w $i$-tej modyfikacji xxx zmienia ocenę estetyczną wierzchołka $p_i$ na $w_i$.
Wyjście
Na początku oraz po każdej modyfikacji wypisz $1$ linię odpowiedzi. Łącznie należy wypisać $q+1$ linii. Każda linia powinna zawierać dwie liczby: „maksymalną sumę ocen estetycznych podgrafu” oraz „liczbę różnych $k$-magicznych podgrafów, których suma ocen estetycznych osiąga wartość maksymalną (modulo $64123$)”.
Przykład
Wejście 1
5 5 2 1 2 1 2 2 2 3 2 1 1 4 1 3 1 5 1 2 1
Wyjście 1
6 4 5 5
Uwagi
Na początku istnieją $4$ sposoby uzyskania maksymalnej sumy ocen estetycznych równej $6$:
| Numer | $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)\}$ |
Po zmianie oceny estetycznej wierzchołka $2$ na $1$, istnieje $5$ sposobów uzyskania maksymalnej sumy ocen estetycznych równej $5$:
| Numer | $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)\}$ |
Ograniczenia
Dla wszystkich danych wejściowych gwarantuje się, że $n \ge 2, m, q \ge 0, 2 \le k \le 3, 1 \le v_i, w_i \le 5000$.
Szczegółowe informacje o podzadaniach znajdują się w poniższej tabeli:
| Podzadanie | Punkty | Testy | $n$ | $m$ | $k$ | $q$ | Własność |
|---|---|---|---|---|---|---|---|
| 1 | 7 | 1 | $\le 10$ | $\le 20$ | $= 3$ | $\le 100$ | brak |
| 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$ | brak |
| 8 | 14 | 14,15 | $\le 100000$ | $\le 300000$ | $= 3$ | $=0$ | brak |
| 9 | 3 | 16 | $\le 30000$ | $\le 55000$ | $=3$ | $\le 10000$ | brak |
| 10 | 10 | 17~20 | $\le 30000$ | $\le 100000$ | $=3$ | $\le 10000$ | brak |
Własność 1: Gwarantuje się, że $G$ jest drzewem o $n$ wierzchołkach. Własność 2: Gwarantuje się, że wszystkie $v_i, w_i$ są równe $1$. Własność 3: Dla dowolnego zbioru $V'$ składającego się z $5$ wierzchołków z $V$, istnieją trzy różne wierzchołki $p, q \in V'$ oraz $x \in V-\{p, q\}$ takie, że po usunięciu wierzchołka $x$ z grafu, $p$ i $q$ stają się niespójne.
Dla każdego testu, jeśli pierwsza liczba w każdej linii jest poprawna, ale druga liczba w niektórych liniach jest błędna, nadal możesz otrzymać $60\%$ punktów za ten test. (Jeśli nie zamierzasz odpowiadać na drugie pytanie, możesz wypisać dowolną liczbę jako drugą wartość).