题目描述

B 市共有 $m$ 个地铁站，编号为 $1$ 到 $m$。每个地铁站都有一个站厅，地铁口与站厅之间有一条通道，往返耗时相同。从第 $v$ 个地铁站的地铁口走到站厅需要 $w_v$ 的时间。

B 市共有 $n$ 条地铁线路，编号为 $1$ 到 $n$，其中第 $i$ 条线路经过 $k_i$ 个地铁站，编号依次为 $a_{i,1},a_{i,2},\ldots,a_{i,k_i}$。在第 $a_{i,j}$ 个地铁站处，从站厅走到第 $i$ 条线路的站台需要 $t_{i,j}$ 的时间，往返耗时相同。同一条线路不会重复经过同一个地铁站。

每个地铁站最多有 $d$ 条线路经过。地铁网络是连通的，即任意两个地铁站都可以通过若干条线路互相到达。

小 R 有 $q$ 个出行计划。对于第 $r$ 个出行计划，小 R 将从第 $x_r$ 个地铁站的地铁口出发，乘坐地铁到达第 $y_r$ 个地铁站的地铁口，途中可能进行若干次站内换乘。每次站内换乘都需要从一条线路的站台先走到站厅，再从站厅走到另一条线路的站台。每个出行计划的总步行时间为进出站和换乘的步行时间之和。

请你求出每个出行计划的最小总步行时间。

输入格式

第一行包含五个非负整数 $c,n,m,d,q$，分别表示测试点编号、地铁线路数、地铁站数、每个地铁站最多被几条线路经过，以及出行计划数。若 $c=0$，则该测试点为样例。

第二行包含 $m$ 个正整数 $w_1,w_2,\ldots,w_m$。

接下来 $n$ 行，第 $i$ 行首先包含正整数 $k_i$，接着包含 $2k_i$ 个正整数 $a_{i,1},t_{i,1},a_{i,2},t_{i,2},\ldots,a_{i,k_i},t_{i,k_i}$。

接下来 $q$ 行，第 $r$ 行包含两个正整数 $x_r,y_r$，表示该出行计划的起点和终点站编号。

输出格式

输出 $q$ 行，第 $r$ 行包含一个非负整数，表示第 $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

数据范围

对于所有测试数据：

• $0\le c\le25$，$1\le n\le500$，$1\le m\le\sum_{i=1}^{n}k_i\le5\times10^5$，$1\le d\le20$，$1\le q\le10^5$。
• $1\le w_v\le10^9$；$1\le k_i\le m$；$1\le a_{i,j}\le m$，$1\le t_{i,j}\le10^9$。
• 同一线路经过的地铁站两两不同；每站经过的线路数不超过 $d$；地铁网络连通。
• $1\le x_r,y_r\le m$，且 $x_r\ne y_r$。

特殊性质 A：每条线路至多经过 $2$ 个地铁站，即对所有 $i$ 均有 $k_i\le2$。

特殊性质 B：存在正整数 $T$，使得对所有 $i,j$ 均有 $t_{i,j}=T$。