「你走吧 趁着落日长天」 「你走吧 此去山遥路远」 「敢想你策马挥鞭」 「绝尘不见」

$n$ 個の頂点と $m$ 本の辺からなる有向グラフが与えられます。各有向辺には長さ $w$ があり、さらに文字が割り当てられています。この文字は左括弧 ( または右括弧 ) のいずれかです。

あるパスが「合法」であるとは、そのパスが通るすべての辺の文字を順に連結して得られる括弧列が、合法な括弧列であることを指します。

次に $q$ 個のクエリが与えられます。各クエリでは頂点 $s, t$ が与えられ、$s$ から $t$ への合法なパスが存在するかを判定します。存在する場合は、その最短の合法パスの長さを求めてください。答えは非常に大きくなる可能性があるため、結果を $998244353$ で割った余りを出力してください。

このグラフには多重辺や自己ループが含まれる可能性があることに注意してください。

入力

1行目には3つの正整数 $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$ へは長さ $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$ です。これより短いものは存在しません。結果を $998244353$ で割った余りを出力する必要があるため、$10^9 \pmod{998244353} = 1755647$ を出力します。

制約

すべてのデータにおいて、$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$ である。