Условие задачи

Предыстория

В бескрайних просторах цифрового лабиринта, где каждый поворот скрывает тайну, а каждый путь — это лишь эхо невысказанных слов, странник ищет гармонию. Он идет по ребрам графа, собирая символы, словно лепестки цветов, надеясь, что в конце пути они сложатся в идеальный узор — правильную скобочную последовательность. Но лабиринт коварен, и лишь кратчайший из верных путей откроет ему истину.

Дан вам ориентированный граф с $n$ вершинами и $m$ ребрами. Каждое ребро имеет длину $w$ и помечено символом, который может быть либо открывающей скобкой (, либо закрывающей скобкой ).

Путь называется правильным, если последовательность символов, полученная при прохождении всех ребер пути, является правильной скобочной последовательностью.

Вам дано $q$ запросов. Каждый запрос задается парой вершин $s, t$. Требуется определить, существует ли правильный путь из $s$ в $t$. Если такой путь существует, выведите длину кратчайшего из них. Поскольку ответ может быть очень большим, выведите его по модулю $998244353$.

Обратите внимание, что в графе могут быть кратные ребра и петли.

Входные данные

Данные считываются из файла distant.in.

Первая строка содержит три целых положительных числа $n, m, q$, значения которых описаны выше.

Далее следуют $m$ строк, каждая из которых содержит четыре целых числа $u, v, w, t$, где $u$ и $v$ — начальная и конечная вершины ребра, $w$ — его длина, а $t = 1$ означает открывающую скобку (, в противном случае $t = 2$ означает закрывающую скобку ).

Далее следуют $q$ строк, каждая из которых содержит два целых числа $s, t$ — запрос для пары вершин.

Выходные данные

Результат записывается в файл distant.out.

Всего выводится $q$ строк. В каждой строке выведите одно целое число: если правильного пути не существует, выведите $-1$, в противном случае выведите длину кратчайшего пути по модулю $998244353$.

Примеры

Пример 1

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

Выходные данные 1

0
-1
200000000
600000000
1755647

Пояснение к примеру

Запрос $(1, 1)$: для пути из $1$ в $1$ достаточно пути длины $0$, который является пустой последовательностью, а пустая последовательность сама по себе является правильной.

Запрос $(1, 2)$: фактически, любой путь из $1$ в $2$ является неправильным, поэтому выводим $-1$.

Запрос $(1, 3)$: $1 \to 2 \to 3$ — это правильный путь, скобочная последовательность (), длина $2 \times 10^8$, короче пути нет.

Запрос $(1, 4)$: $1 \to 2 \to 3 \to 1 \to 2 \to 3 \to 4$ — это правильный путь, скобочная последовательность ()(()), длина $6 \times 10^8$, короче пути нет.

Запрос $(1, 5)$: $1 \to 2 \to 3 \to 1 \to 2 \to 3 \to 1 \to 2 \to 3 \to 4 \to 5$ — это правильный путь, скобочная последовательность ()(()(())), длина $10^9$, короче пути нет. Обратите внимание, что мы выводим результат по модулю, поэтому $10^9 \pmod{998244353} = 1755647$.

Примеры 2~3

См. файлы distant/distant2~3.in и distant/distant2~3.ans в директории участника.

Подзадачи

Special constraint A: Для всех подзадач гарантируется $1 \le n \le 400, 1 \le m \le 5 \times 10^4, 1 \le q \le 10^5, 0 \le w \le 10^8$.