Background

A second-year student, all alone.

Looking up at the sky above, the gray city’s dome.

In this dating room called the universe,

Maybe we just happened to not meet.

Problem Description

A famous engineering expert, 625OutContradiction, designed a subway transportation network $G$. $G$ has $n$ stations and $m$ subway lines.

The $i$-th subway line $P_i$ passes through several stations in the transportation network, in the form $P_i=(u_1,u_2,u_3,\ldots,u_{k_i})(k_i>0)$. Between every two adjacent stations $u_j,u_{j+1}(j<k_i)$, there is a one-way subway track belonging to line $i$ that goes from $u_j$ to $u_{j+1}$. It is guaranteed that a subway line does not pass through the same station more than once. However, a station may be passed through by multiple subway lines.

Danyu and Eriou are going from station $1$ to station $n$. However, their bicycle broke, so they have to take the subway. Now they need to decide a travel plan.

A travel plan works like this: starting from station $1$, choose a subway line that passes through station $1$ and start riding. While riding along the current subway line, you may choose to transfer to any other subway line that passes through the current station. You must finally reach station $n$. During the ride, it is allowed to visit a station or a subway track multiple times.

Note: when departing from station $1$, the first time you take the subway is not counted as a transfer.

Eriou asks $q$ questions. For each question, Eriou provides three parameters $a, b, c$. In this question, if a travel plan passes through $x$ subway tracks and makes $y$ transfers, then its fatigue value is $ax+by$. You need to answer: among travel plans with no more than $c$ transfers, what is the minimum fatigue value.

Input Format

The first line contains three integers $n, m, q$.

The next $m$ lines describe the subway lines. The $i$-th line is in the form: $k_i,u_1,u_2,u_3,\ldots,u_{k_i}$, representing one subway line.

The next $q$ lines each contain three integers, representing $a,b,c$.

Output Format

Output $q$ lines, each corresponding to the answer for one question.

5 3 3
5 1 2 3 4 5
2 1 3
3 2 4 5
1 1 1
3 0 2
1 5 2

4
9
4

10 7 10
10 1 2 3 4 5 6 7 8 9 10
5 3 8 5 1 6
2 1 6
4 3 7 8 5
1 1
2 10 2
6 8 4 7 3 1 5
5 10 6
17 14 0
11 14 5
8 8 3
8 13 9
11 2 9
7 1 6
11 11 8
15 3 0
0 17 4

35
153
69
48
53
57
36
66
135
0

10 7 10
10 1 2 3 4 5 6 7 8 9 10
3 2 7 1
3 5 10 9
2 2 7
5 4 8 1 7 2
3 10 9 4
4 2 1 7 8
18 6 0
16 11 0
18 1 0
14 0 0
19 14 0
3 2 0
18 15 0
5 18 0
2 17 0
20 10 0

162
144
162
126
171
27
162
45
18
180

Hint

Sample #1 Explanation

$1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5$ is the first given subway line. $1\rightarrow 3$ and $2\rightarrow 4\rightarrow 5$ are the second and third subway lines.

For the first two queries, there is an optimal travel plan: take the second subway line from station $1$ to station $3$, then transfer at station $3$ to the first subway line to reach the destination. In total, it passes through $3$ subway tracks and makes $1$ transfer, so the answers for the first two queries are $3\times 1+1\times 1=4$ and $3\times 3+1\times 0=9$, respectively. For the third query, since transfers are expensive, the optimal plan is to follow the first subway line all the way to the destination, passing through $4$ subway tracks, so the answer is $4$.

Constraints

For all data:

$1\le n \le 10^5$, $1\le m \le 10^4$, $1\le q \le 10^5$, $\sum k_i \le 3\times 10^5$.

$0 \le a,b \le 10^6$, $0 \le c \le 20$.

For $10\%$ of the data: $n \le 20$, $\sum k_i \le 40$, $q \le 30$.

For another $20\%$ of the data: $c=0$.

For another $30\%$ of the data: $q=1$.

There may be subway lines in the problem that pass through only one station. Such lines can be ignored directly. The testdata guarantees that for any query, there exists a valid route that can reach the destination.

Translated by ChatGPT 5