Taking the Metro (Large)

Tom rides the city metro to get from one station to another.

The metro system works like this.

• The city has $N$ metro lines, numbered 1 to $N$.
• Line $i$ has $SN_i$ stations, written $S_{i,1}, S_{i,2}, \dots, S_{i,SN_i}$ in order from one end of the line to the other. Trains run in both directions, so a train goes $S_{i,1} \to S_{i,2} \to \dots \to S_{i,SN_i}$ and another goes $S_{i,SN_i} \to S_{i,SN_i-1} \to \dots \to S_{i,1}$. You can board at any station and get off at any station. Riding from $S_{i,j}$ to $S_{i,j+1}$ takes $\text{Time}_{i,j}$ minutes, and the same ride in the opposite direction takes the same time.
• There are $M$ transfer tunnels. Each tunnel connects two stations that belong to different lines, and walking through it takes the same time in either direction. You get off a train at one end of a tunnel, walk through the tunnel, and arrive at the station at the other end.
• Every time you board a train of line $i$, you wait $W_i$ minutes for that train. Staying on a train while it passes a station costs no extra time, and getting off costs no time.

You start at one station and travel to another one. Find the shortest total time.

The first line holds the number of test cases $T$. The test cases follow.

Each test case starts with a line holding $N$, the number of metro lines. Descriptions of the $N$ lines follow. The description of line $i$ starts with a line holding two integers $SN_i$ and $W_i$, the number of stations and the waiting time in minutes. The next line holds $SN_i - 1$ integers $\text{Time}_{i,1}, \text{Time}_{i,2}, \dots, \text{Time}_{i,SN_i-1}$, the riding times between neighboring stations.

After the line descriptions comes a line holding $M$, the number of transfer tunnels, then $M$ lines. Each of them holds five integers $m1_i$, $s1_i$, $m2_i$, $s2_i$, $t_i$, meaning that a tunnel connects station $S_{m1_i, s1_i}$ and station $S_{m2_i, s2_i}$, and that walking through that tunnel takes $t_i$ minutes.

The next line holds $Q$, the number of queries, followed by $Q$ lines. Each of them holds four integers $x_1$, $y_1$, $x_2$, $y_2$, meaning that you travel from station $S_{x_1,y_1}$ to station $S_{x_2,y_2}$.

Limits:

• $1 \le T \le 100$
• $1 \le N \le 100$
• $2 \le SN_i \le 1000$, and one test case has at most 1000 stations in total
• $1 \le W_i \le 100$
• $1 \le \text{Time}_{i,j} \le 100$
• $0 \le M \le 100$
• $1 \le m1_i \le N$, $1 \le s1_i \le SN_{m1_i}$, $1 \le m2_i \le N$, $1 \le s2_i \le SN_{m2_i}$, and $m1_i \ne m2_i$
• $1 \le t_i \le 100$
• $1 \le Q \le 10$
• $1 \le x_1 \le N$, $1 \le y_1 \le SN_{x_1}$, $1 \le x_2 \le N$, $1 \le y_2 \le SN_{x_2}$
• Station $S_{x_1,y_1}$ and station $S_{x_2,y_2}$ are different

For each test case, print one line holding Case #x:, where x is the test case number starting from 1. Then print $Q$ lines. The $k$-th of them holds the shortest time for the $k$-th query, or -1 when the destination cannot be reached.

In the first query of the first test case of the sample input you go from station 1 of line 1 to station 4 of line 2. One shortest route is:

• Wait 3 minutes for a train of line 1 and board it.
• Ride 3 minutes and get off at station 2.
• Walk the tunnel for 1 minute to station 2 of line 2.
• Wait 2 minutes for a train of line 2 and board it.
• Ride 2 minutes and get off at station 4.

The total time is 3 + 3 + 1 + 2 + 2 = 11.