xxx очень любит задачи по теории графов. Недавно его хорошие друзья y0rkllu и y0rklld подарили ему подарок — неориентированный граф $G=(V,E)$ без петель и кратных ребер, где $n=|V|, m=|E|$. Интересно, что для любого подмножества $V'$ из $7$ вершин графа существуют три различные вершины $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 хочет выбрать $k$-волшебный подграф $G'=(V',E'), V'\subseteq V, E'\subseteq E$ в качестве украшения для своего дома. В графе для каждой вершины определена оценка красоты $v_p$. Естественно, xxx хочет, чтобы сумма оценок красоты всех вершин в этом подграфе была максимальной. Кроме того, он не любит повторений и хочет, чтобы украшение каждый день было разным. Поэтому он просит вас помочь ему найти максимальную сумму оценок красоты среди всех $k$-волшебных подграфов графа $G$, а также количество различных $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$, обозначающих количество вершин, количество ребер в простом графе $G$ и значение $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$, количество изменений оценок красоты.
Следующие $q$ строк содержат по два целых числа $p_i, w_i$, означающих, что в $i$-м изменении xxx меняет оценку красоты вершины $p_i$ на $w_i$.
Выходные данные
Выведите по одной строке ответов для начального состояния и после каждого изменения, итого $q+1$ строк. Каждая строка должна содержать два числа: «максимальная сумма оценок красоты $k$-волшебного подграфа» и «количество различных $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
Примечание
В начальный момент существует $4$ варианта с максимальной суммой оценок красоты $6$:
| Номер | $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$ вершин графа существуют три различные вершины $p,q\in V',x\in V-\{p,q\}$ такие, что после удаления вершины $x$ из графа вершины $p$ и $q$ становятся несвязными.
Для каждого теста, если вы правильно вывели первое число в каждой строке, но ошиблись во втором, вы все равно получите $60\%$ баллов за этот тест. (Если вы не планируете отвечать на второй вопрос, можете выводить любое число в качестве второго).