cho.sh

Taking the Metro (Large)

Find the fastest route between two metro stations where each boarding adds a line waiting time and transfers use walking tunnels.

Medium5Shortest pathGraphNo attempts yetTime limit5sMemory limit512 MB

Problem

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

The metro system works like this.

  • The city has NN metro lines, numbered 1 to NN.
  • Line ii has SNiSN_i stations, written Si,1,Si,2,…,Si,SNiS_{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 Si,1→Si,2→⋯→Si,SNiS_{i,1} \to S_{i,2} \to \dots \to S_{i,SN_i} and another goes Si,SNi→Si,SNi−1→⋯→Si,1S_{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 Si,jS_{i,j} to Si,j+1S_{i,j+1} takes Timei,j\text{Time}_{i,j} minutes, and the same ride in the opposite direction takes the same time.
  • There are MM 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 ii, you wait WiW_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.

Input

The first line holds the number of test cases TT. The test cases follow.

Each test case starts with a line holding NN, the number of metro lines. Descriptions of the NN lines follow. The description of line ii starts with a line holding two integers SNiSN_i and WiW_i, the number of stations and the waiting time in minutes. The next line holds SNi−1SN_i - 1 integers Timei,1,Timei,2,…,Timei,SNi−1\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 MM, the number of transfer tunnels, then MM lines. Each of them holds five integers m1im1_i, s1is1_i, m2im2_i, s2is2_i, tit_i, meaning that a tunnel connects station Sm1i,s1iS_{m1_i, s1_i} and station Sm2i,s2iS_{m2_i, s2_i}, and that walking through that tunnel takes tit_i minutes.

The next line holds QQ, the number of queries, followed by QQ lines. Each of them holds four integers x1x_1, y1y_1, x2x_2, y2y_2, meaning that you travel from station Sx1,y1S_{x_1,y_1} to station Sx2,y2S_{x_2,y_2}.

Limits:

  • 1≤T≤1001 \le T \le 100
  • 1≤N≤1001 \le N \le 100
  • 2≤SNi≤10002 \le SN_i \le 1000, and one test case has at most 1000 stations in total
  • 1≤Wi≤1001 \le W_i \le 100
  • 1≤Timei,j≤1001 \le \text{Time}_{i,j} \le 100
  • 0≤M≤1000 \le M \le 100
  • 1≤m1i≤N1 \le m1_i \le N, 1≤s1i≤SNm1i1 \le s1_i \le SN_{m1_i}, 1≤m2i≤N1 \le m2_i \le N, 1≤s2i≤SNm2i1 \le s2_i \le SN_{m2_i}, and m1i≠m2im1_i \ne m2_i
  • 1≤ti≤1001 \le t_i \le 100
  • 1≤Q≤101 \le Q \le 10
  • 1≤x1≤N1 \le x_1 \le N, 1≤y1≤SNx11 \le y_1 \le SN_{x_1}, 1≤x2≤N1 \le x_2 \le N, 1≤y2≤SNx21 \le y_2 \le SN_{x_2}
  • Station Sx1,y1S_{x_1,y_1} and station Sx2,y2S_{x_2,y_2} are different

Output

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

Hint

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.