题目背景

两年级生 孤单一人

仰望上空 陋市苍穹

在宇宙这个约会室中

Maybe 我们只是刚好没能邂逅呢

题目描述

著名工程学专家 625OutContradiction 设计了一张地铁交通网 $G$．$G$ 拥有 $n$ 个站点和 $m$ 条地铁线路．

第 $i$ 条地铁线路 $P_i$ 会经过交通网上的若干站点，形如 $P_i=(u_1,u_2,u_3,...,u_{k_i})(k_i>0)$：每两个相邻站点 $u_j,u_{j+1}(j<k_i)$ 之间存在一段属于线路 $i$ 的从 $u_j$ 通向 $u_{j+1}$ 的单向地铁轨道．保证一条地铁线路不重复经过同一站点．但一个站点可能被若干条地铁线路经过．

丹羽和艾莉欧准备从 $1$ 号站点前往 $n$ 号站点．然而他们的自行车坏掉了，只好准备乘坐地铁．现在他们需要决定出行的方案．

一种出行方案具体是这样的：从 $1$ 号站点出发，选定一条经过 $1$ 号站点的地铁线路并开始乘坐地铁．沿当前地铁线路乘坐地铁的过程中，可以选择换乘其他任意一条经过当前站点的地铁线路．要求最终到达 $n$ 号站点．乘坐地铁过程中重复经过某一站点或某段地铁轨道是被允许的．

请注意：从 $1$ 号站点出发，第一次乘坐地铁不被算作换乘．

艾莉欧提出了 $q$ 个问题．对于每个问题，艾莉欧会提供三个参数 $a, b, c$．在这次问题中，一个出行方案如果经过了 $x$ 段地铁轨道并进行了 $y$ 次换乘，那么它的疲惫值为 $ax+by$．您需要回答换乘次数不超过 $c$ 的出行方案中最小的疲惫值是多少．

输入格式

第一行三个整数 $n, m, q$．

接下来 $m$ 行，第 $i$ 行形如：$k_i,u_1,u_2,u_3,...,u_{k_i}$． 表示一条地铁线路．

接下来 $q$ 行，每行三个整数，表示 $a,b,c$．

输出格式

$q$ 行，对应每个问题的回答．

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

提示

样例 #1 说明

$1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5$ 是给出的第一条地铁线路，$1\rightarrow 3$，$2\rightarrow 4\rightarrow 5$ 是第二三条地铁线路．

对于第一二组询问，均存在一种最优的出行方案为，在 $1$ 站点搭乘第二条地铁线路到达 $3$ 站点，在 $3$ 站点换乘第一条地铁线路到达终点；共经过 $3$ 段地铁轨道，并进行了 $1$ 次换乘，故第一二组询问的答案分别为 $3\times 1+1\times 1=4$，$3\times 3+1\times 0=9$．对于第三组询问，由于换乘的代价较大，最优的方案为顺着第一条地铁线路一直通向终点，途径 $4$ 段地铁轨道，答案为 $4$．

数据点约束

对于所有数据满足：

$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$．

对于 $10\%$ 的数据满足：$n \le 20$，$\sum k_i \le 40$，$q \le 30$．

对于另外 $20\%$ 的数据满足：$c=0$．

对于另外 $30\%$ 的数据满足：$q=1$．

题目中可能存在只经过一个地铁站的地铁线路．这种线路可以直接忽视．数据保证：对于任意一组询问，存在一条合法的路线可以到达终点．