「你走吧 趁着落日长天」

「你走吧 此去山遥路远」

「敢想你策马挥鞭」

「绝尘不见」

给你一个 $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$ 只需要一条长度为 $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$。

对于 $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$。