Background

A second-year student, alone
Gazing at the sky, the dilapidated city
In the universe, this rendezvous room
Maybe we just happened not to meet

Problem Description

Renowned engineering expert 625OutContradiction has designed a subway network \( G \). \( G \) consists of \( n \) stations and \( m \) subway lines.

The \( i \)-th subway line \( P_i \) passes through several stations in the network, denoted as \( P_i = (u_1, u_2, u_3, ..., u_{k_i}) \) where \( k_i > 0 \): each pair of adjacent stations \( u_j, u_{j+1} \) (where \( j < k_i \)) has a one-way subway track from \( u_j \) to \( u_{j+1} \) belonging to line \( i \). It is guaranteed that a subway line does not repeat through the same station, but a station may be passed through by multiple subway lines.

Niwa and Erio plan to travel from station 1 to station \( n \). However, their bicycle broke down, so they have to take the subway. Now they need to decide on a travel plan.

A travel plan is as follows: Starting from station 1, choose a subway line that passes through station 1 and begin riding. During the journey on the current subway line, one can choose to transfer to any other subway line that passes through the current station. The goal is to eventually reach station \( n \). Repeating through a station or a subway track is allowed during the journey.

Note: The first ride from station 1 is not considered a transfer.

Erio has posed \( q \) questions. For each question, Erio provides three parameters \( a, b, c \). In this question, if a travel plan passes through \( x \) subway tracks and makes \( y \) transfers, its fatigue value is \( ax + by \). You need to answer the minimum fatigue value among travel plans with no more than \( c \) transfers.

Input Format

The first line contains three integers \( n, m, q \).

The next \( m \) lines, the \( i \)-th line is in the form: \( k_i, u_1, u_2, u_3, ..., u_{k_i} \).
This represents a subway line.

The next \( q \) lines, each containing three integers, represent \( a, b, c \).

Output Format

\( q \) lines, corresponding to the answers for each question.

Sample Input and Output

Input Sample #1

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

Output Sample #1

4
9
4

Input Sample #2

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

Output Sample #2

35
153
69
48
53
57
36
66
135
0

Input Sample #3

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

Output Sample #3

162
144
162
126
171
27
162
45
18
180

Notes

Sample #1 Explanation

The first subway line is \( 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \), the second line is \( 1 \rightarrow 3 \), and the third line is \( 2 \rightarrow 4 \rightarrow 5 \).

For the first two queries, an optimal travel plan is to take the second line from station 1 to station 3, then transfer to the first line to reach the destination; this involves passing through 3 subway tracks and making 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 \). For the third query, since the cost of transfers is high, the optimal plan is to follow the first line directly to the destination, passing through 4 subway tracks, with an answer of 4.

Data 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 \).

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

见题面 Input 部分

见题面 Output 部分