B 市共有 m 个地铁站，编号为 1 到 m。每个地铁站都有一个站厅，地铁口与站厅之间有一条通道，往返耗时相同。从第 v（1 \le v \le m）个地铁站的地铁口走到站厅需要 w_v 的时间。
B 市共有 n 条地铁线路，编号为 1 到 n，其中第 i（1 \le i \le n）条线路经过 k_i 个地铁站，编号依次为 a_{i,1}, a_{i,2}, \ldots, a_{i,k_i}。在第 a_{i,j}（1 \le j \le k_i）个地铁站处，从站厅走到第 i 条线路的站台需要 t_{i,j} 的时间，往返耗时相同。同一条线路不会重复经过同一个地铁站，即 a_{i,1}, a_{i,2}, \ldots, a_{i,k_i} 两两不同。
由于空间有限，每个地铁站最多有 d 条线路经过。此外，B 市的地铁网络是连通的，即任意两个地铁站都可以通过若干条线路互相到达。
小 R 有 q 个出行计划。对于第 r（1 \le r \le q）个出行计划，小 R 将从第 x_r 个地铁站的地铁口出发，乘坐地铁到达第 y_r 个地铁站的地铁口，途中可能进行若干次站内换乘。每次站内换乘都需要从一条线路的站台先走到站厅，再从站厅走到另一条线路的站台。每个出行计划的总步行时间为进出站和换乘的步行时间之和。小 R 希望每个出行计划的总步行时间都尽可能少。
你需要帮助小 R 求出，每个出行计划的最小总步行时间。
输入的第一行包含五个非负整数 c, n, m, d, q，分别表示测试点编号、地铁线路数、地铁站数、每个地铁站最多被几条线路经过，以及出行计划数。特别地，若 c = 0，则该测试点为样例。
输入的第二行包含 m 个正整数 w_1, w_2, \ldots, w_m，依次表示从每个地铁站的地铁口走到站厅需要的时间。
输入的第 i + 2（1 \le i \le n）行包含 1 + 2k_i 个正整数，其中第一个正整数为 k_i，表示第 i 条线路经过的地铁站数；接下来 2k_i 个正整数为 a_{i,1}, t_{i,1}, a_{i,2}, t_{i,2}, \ldots, a_{i,k_i}, t_{i,k_i}，其中 a_{i,j} 表示第 i 条线路经过的第 j 个地铁站，t_{i,j} 表示从该地铁站的站厅走到第 i 条线路的站台需要的时间。
输入的第 r + n + 2（1 \le r \le q）行包含两个正整数 x_r, y_r，分别表示第 r 个出行计划的起点和终点所在的地铁站编号。
输出 q 行，其中第 r（1 \le r \le q）行包含一个非负整数，表示第 r 个出行计划的最小总步行时间。
0 2 5 20 2 4 1 9 2 5 3 1 5 2 7 4 6 3 2 3 3 4 5 7 1 3 1 2
32 17
0 3 7 20 2 8 3 6 1 7 2 9 3 1 4 2 5 5 100 3 2 6 3 1 7 2 4 3 2 5 100 4 6 6 7 1 6 2 3
35 16
样例 1 解释：对于第 1 个出行计划（从第 1 站到第 3 站），总步行时间为
对于第 2 个出行计划（从第 1 站到第 2 站），不用换乘，总步行时间为 w_1 + t_{1,1} + t_{1,2} + w_2 = 4 + 5 + 7 + 1 = 17。
数据范围：对于所有测试数据，均有：
• 0 \le c \le 25，1 \le n \le 500，1 \le m \le \sum_{i=1}^{n} k_i \le 5 \times 10^5，1 \le d \le 20，1 \le q \le 10^5；
• 对于所有 v（1 \le v \le m），均有 1 \le w_v \le 10^9；
• 对于所有 i（1 \le i \le n），均有 1 \le k_i \le m；
• 对于所有 i, j，均有 1 \le a_{i,j} \le m，1 \le t_{i,j} \le 10^9；
• 经过每个地铁站的线路数不超过 d，任意两个地铁站都互相可达；
• 对于所有 r，均有 1 \le x_r, y_r \le m，且 x_r \ne y_r。
本题共 25 个等分测试点，每点 4 分。
| 测试点编号 | n ≤ | ∑k_i ≤ | d ≤ | q ≤ | 特殊性质 |
|---|---|---|---|---|---|
| 1 ~ 3 | 3 | 10 | 20 | 10 | 无 |
| 4 ~ 6 | 50 | 300 | 20 | 200 | 无 |
| 7, 8 | 200 | 400 | 20 | 200 | A |
| 9 ~ 11 | 500 | 1000 | 20 | 105 | A |
| 12 ~ 15 | 500 | 2 × 104 | 20 | 2000 | B |
| 16 ~ 19 | 500 | 5 × 105 | 20 | 105 | B |
| 20, 21 | 2 | 5 × 105 | 20 | 105 | 无 |
| 22, 23 | 500 | 5 × 105 | 2 | 105 | 无 |
| 24, 25 | 500 | 5 × 105 | 20 | 105 | 无 |
特殊性质 A：每条线路至多经过 2 个地铁站，即对于所有 i，均有 k_i \le 2。
特殊性质 B：存在正整数 T，使得对于所有 i, j，均有 t_{i,j} = T。
附加样例：官方题面另有样例 3 ~ 7 共五组大样例（分别满足测试点 4~6、9~11、12~15、16~19、22,23 的约束），因数据量较大未在此列出。
提示
乘车本身不计入步行时间，所以「同一条线路上的任意两站」之间步行代价为 0。把线路而不是地铁站看成图的点会更清爽：两条线路若有公共站，它们之间换乘的代价就是 \min (t_{L,x} + t_{M,x}（对所有公共站 x 取最小值）。线路数只有 500，可以直接 Floyd（或者 500 次 Dijkstra）求出线路之间的最小换乘代价 D(L, M)。
一次从 x 到 y 的出行 = 进 + 若干次换乘 + 出。枚举「从 x 上车的线路 L」和「到 y 下车的线路 M」，答案形如 w_x + t_{L,x} + D(L, M) + t_{M,y} + w_y。每站最多 d \le 20 条线路，所以单次询问的枚举量不超过 d^2 = 400，注意把 x、y 中经过线路较少的一端放在外层循环，并且把 L = M（不换乘）的情况包含进去。
线路与站点之间是「二部图」关系：预处理每个站经过哪些线路（把同一站的线路排在一起即可快速枚举线路对），总规模只有 \sum k_i，不会超过 5 \times 10^5。