Tło problemu
W krainie, gdzie liczby w tańcu się splatają, Gdzie nawiasy ścieżki swe wyznaczają, Wierzchołek z wierzchołkiem więzią się łączy, Kto najkrótszą drogę znajdzie, ten wyścig ukończy. Niech suma wag wskaże nam cel, Gdy nawiasy w parę układają się w tle.
Dany jest skierowany graf o $n$ wierzchołkach i $m$ krawędziach. Każda krawędź ma przypisaną wagę $w$ oraz znak, którym jest nawias otwierający ( lub zamykający ).
Ścieżkę nazywamy poprawną, jeśli ciąg znaków powstały z połączenia wszystkich znaków na krawędziach tej ścieżki tworzy poprawny ciąg nawiasowy.
Dostępnych jest $q$ zapytań. W każdym zapytaniu podane są wierzchołki $s$ i $t$. Należy sprawdzić, czy istnieje poprawna ścieżka z $s$ do $t$. Jeśli tak, należy wypisać długość najkrótszej takiej ścieżki. Ponieważ wynik może być bardzo duży, należy wypisać go modulo $998244353$.
Graf może zawierać krawędzie wielokrotne oraz pętle własne.
Wejście
W pierwszej linii wejścia znajdują się trzy liczby całkowite $n, m, q$, oznaczające odpowiednio liczbę wierzchołków, krawędzi oraz zapytań.
Następnie podano $m$ linii, z których każda zawiera cztery liczby całkowite $u, v, w, t$. Oznaczają one skierowaną krawędź z $u$ do $v$ o wadze $w$. Jeśli $t = 1$, krawędź jest nawiasem otwierającym (, w przeciwnym razie ($t = 2$) jest nawiasem zamykającym ).
Następnie podano $q$ linii, z których każda zawiera dwie liczby całkowite $s, t$, określające zapytanie o ścieżkę z $s$ do $t$.
Wyjście
Dla każdego z $q$ zapytań wypisz w osobnej linii wynik. Jeśli poprawna ścieżka nie istnieje, wypisz $-1$. W przeciwnym razie wypisz długość najkrótszej ścieżki modulo $998244353$.
Przykład
Wejście 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
Wyjście 1
0 -1 200000000 600000000 1755647
Wyjaśnienie 1
Dla zapytania (1, 1) najkrótsza ścieżka ma długość 0 (pusty ciąg jest poprawnym ciągiem nawiasowym). Dla zapytania (1, 4) ścieżka 1 -> 2 -> 3 -> 4 tworzy ciąg ()(), co jest poprawnym ciągiem nawiasowym, a suma wag wynosi $10^8 + 10^8 + 10^8 = 3 \times 10^8$.
Podzadania
Dla 100% danych wejściowych zachodzą warunki: $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$.
| Test | Punkty | $n$ | $m$ | Ograniczenia specjalne |
|---|---|---|---|---|
| 1 | 25 | $\le 10$ | $\le 10^2$ | |
| 2 | 35 | $\le 10^2$ | $\le 10^3$ | A |
| 3 | 20 | $\le 10^2$ | $\le 10^4$ | |
| 4 | 20 | $\le 400$ | $\le 5 \times 10^4$ |
Ograniczenie specjalne A: gwarantowane $s = 1$.