Metro Travel Fatigue Minimization

A famous engineering expert, 625OutContradiction, has designed a metro network \(G\) consisting of \(n\) stations and \(m\) metro lines.

For each metro line \(i\) (\(1 \le i \le m\)), the line is given as an ordered sequence \(P_i=(u_1, u_2, \dots, u_{k_i})\) with \(k_i>0\). For every consecutive pair \(u_j\) and \(u_{j+1}\) (for \(1 \le j < k_i\)), there is a directed track from \(u_j\) to \(u_{j+1}\) belonging to line \(i\). It is guaranteed that a single line will not visit the same station twice, although a station may be visited by several different lines.

Niwa and Alio need to travel from station \(1\) to station \(n\) by metro (their bicycle is broken!). The travel plan is defined as follows:

• Start at station \(1\) and choose any metro line that passes through station \(1\) (this initial boarding is not considered a transfer).
• While riding on a line, you may decide to switch to any other metro line that passes through the current station. Each such switch is counted as a transfer.
• You may travel along a line using its directed tracks. It is allowed to revisit stations or tracks multiple times.
• The journey must eventually reach station \(n\).

Alio poses \(q\) queries. In each query, three parameters \(a, b, c\) are given. For a given travel plan that uses \(x\) metro tracks (edges) and performs \(y\) transfers (where the initial boarding is not counted), the fatigue value is defined as \(ax+by\). You are to answer, for each query, what is the minimum fatigue value among all travel plans that use at most \(c\) transfers. If station \(n\) is unreachable under the given constraint, output -1.

inputFormat

The input consists of multiple lines:

1. The first line contains two integers \(n\) and \(m\) representing the number of stations and the number of metro lines respectively.
2. The next \(m\) lines describe each metro line. The \(i\)-th such line begins with an integer \(k_i\) (the number of stations on the line), followed by \(k_i\) integers representing the stations in order.
3. The next line contains a single integer \(q\), the number of queries.
4. The following \(q\) lines each contain three integers \(a\), \(b\), and \(c\) representing the cost per track, the cost per transfer, and the maximum number of allowed transfers respectively.

Note: \(\,1 \leq u_j \leq n\,\) and stations are numbered from 1 to \(n\).

outputFormat

For each query, output a single line containing the minimum fatigue value among all valid travel plans that use at most \(c\) transfers. If station \(n\) is unreachable under the given constraints, output -1.

sample

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

2
2