You are given a directed graph with $n$ nodes and $m$ edges. Each directed edge has a length $w$ and a character, which is either an opening parenthesis '(' or a closing parenthesis ')'.

A path is called a valid path if the sequence of characters formed by concatenating the characters on the edges along the path is a valid parenthesis sequence.

There are $q$ queries. For each query, you are given nodes $s$ and $t$. Determine if there exists a valid path from $s$ to $t$. If it exists, output the length of the shortest valid path. Since the answer can be very large, you only need to output the result modulo $998244353$.

Note that the graph may contain multiple edges between the same pair of nodes and self-loops.

Input

The input is read from the file distant.in.

The first line contains three positive integers $n, m, q$, as described in the problem statement.

The next $m$ lines each contain four positive integers $u, v, w, t$, representing a directed edge from $u$ to $v$ with length $w$. If $t = 1$, the character is '(', otherwise if $t = 2$, the character is ')'.

The next $q$ lines each contain two positive integers $s, t$, representing a query from $s$ to $t$.

Output

The output is written to the file distant.out.

Output $q$ lines in total. Each line contains an integer. If no valid path exists, output $-1$. Otherwise, output the shortest distance modulo $998244353$.

Examples

Input 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

Output 1

0
-1
200000000
600000000
1755647

Note 1

Query $(1, 1)$: A path of length $0$ from $1$ to $1$ is just an empty sequence, which is a valid parenthesis sequence.

Query $(1, 2)$: In fact, no path from $1$ to $2$ is valid, so output $-1$.

Query $(1, 3)$: $1 \to 2 \to 3$ is a valid path with the parenthesis sequence $()$, length $2 \times 10^8$, and there is no shorter one.

Query $(1, 4)$: $1 \to 2 \to 3 \to 1 \to 2 \to 3 \to 4$ is a valid path with the parenthesis sequence $()(())$, length $6 \times 10^8$, and there is no shorter one.

Query $(1, 5)$: $1 \to 2 \to 3 \to 1 \to 2 \to 3 \to 1 \to 2 \to 3 \to 4 \to 5$ is a valid path with the parenthesis sequence $()(()(()))$, length $10^9$, and there is no shorter one. Note that we need to output the result modulo $998244353$, so output $10^9 \pmod{998244353} = 1755647$.

Examples 2~3

See distant/distant2~3.in and distant/distant2~3.ans in the contestant directory.

Subtasks

For 100% of the data, $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$.

Special Constraint A: $s = 1$ is guaranteed.