題目背景

「你走吧 趁着落日長天」 「你走吧 此去山遙路遠」 「敢想你策馬揮鞭」 「絕塵不見」

題目敘述

給你一個 $n$ 個點，$m$ 條邊的有向圖，每條有向邊有一個長度 $w$，且上面有一個字元，這個字元只可能是左括號或者右括號，即 ( 或 )。

我們稱一條路徑是合法路徑，滿足其經過的所有字元拼接起來得到的括號串是一個合法括號序列。

接下來有 $q$ 組詢問，每次詢問給出節點 $s, t$，問 $s$ 到 $t$ 是否存在一條合法路徑，如果存在，那麼請輸出其最短合法路徑的長度。由於答案可能很大，你只需要輸出答案模 $998244353$ 的結果。

注意這個圖可能有重邊和自環。

輸入格式

第一行輸入三個正整數 $n, m, q$，含義如題目敘述所示。

接下來輸入 $m$ 行，每行四個正整數 $u, v, w, t$，表示 $u$ 到 $v$ 有一條有向邊，長度為 $w$，$t = 1$ 代表是左括號 (，否則 $t = 2$ 代表是右括號 )。

接下來輸入 $q$ 行，每行兩個正整數 $s, t$，表示 $s$ 到 $t$ 的一組詢問。

輸出格式

共輸出 $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$ 走到 $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。

子任務

對於 $100\%$ 的資料，保證 $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$。

特殊限制 A：保證 $s = 1$。