23030번 - 후다다닥을 이겨 츄르를 받자!

쿠기는 평소 지하철 최단 경로를 탐색하여 소요 시간을 알려주는 '후다다닥' 어플을 사용 중이다. 그러나 쿠기는 걸음이 너무 느려서 '후다다닥'이 알려주는 경로를 따라가면 항상 지하철이 떠나간 빈 플랫폼을 맞이해야 했다.

허탈한 마음에 속상해하던 쿠기는 때마침 창업경진대회가 열린다는 소식을 들었다. 쿠기는 환승 시간과 출발지, 도착지를 입력하면 최단 경로로 이동했을 때 걸리는 소요 시간을 알려주는 어플을 만들어 출품하기로 결심했다.

쿠기가 사는 도시의 지하철 노선은 총 N개가 있으며 1~N까지의 번호로 노선을 구분한다. 각 노선에는 최소 1개, 최대 50개의 역이 있다. 노선에 속한 역에는 가장 왼쪽 끝에 위치한 역을 1번으로 하여 1씩 증가하는 번호가 주어진다. 역 번호가 1씩 차이나는 두 역은 인접하다고 말할 수 있다. 하나의 역에서 인접한 역사이의 거리는 일정하여 지하철을 통해 이동하는 데 모두 1만큼의 시간이 걸린다. 지하철은 양방향 모두 통행이 가능하며, 지하철의 방향을 바꿔타는 시간과 지하철을 타기 위해 대기하는 시간은 걸리지 않는다.

쿠기가 사는 도시의 지하철에는 M개의 환승역이 존재한다. 두 개의 노선이 하나의 역에서 만나는 지점을 환승역이라고 한다. 환승역에 3개 이상의 노선이 겹치는 일은 존재하지 않는다. 환승을 하는 경우 걸어서 이동해야 하므로 사용자는 각자 자신이 환승을 하는 데 걸리는 시간 T를 입력한다. 모든 환승역에서 걸어야 하는 거리는 동일하며, 모든 요청에 대해 항상 도착할 수 있다.

하지만 쿠기는 프로그래밍을 할 줄 모르기 때문에 츄르 100개를 걸고 대신 코드를 짜줄 사람을 찾고 있다.

맛있는 츄르를 얻어보자. 사용자가 환승 시간 T와 출발지, 도착지를 입력하면 최단 경로로 이동하였을 때 걸리는 소요 시간을 알려주는 프로그램을 만들어야 한다.

첫째 줄에 노선의 개수 N(2 ≤ N ≤ 10)이 주어진다.

둘째 줄에 N개의 노선별로 속한 역의 개수가 차례로 주어진다. (1 ≤ 역의 수 ≤ 50)

셋째 줄에 환승역의 개수 M(1 ≤ M ≤ ⌊모든 역의 수 / 2⌋)이 주어진다.

넷째 줄부터 M개의 줄에 환승역의 정보가 주어진다.

각 줄은 네개의 양의 정수 P1, P2, Q1, Q2로 구성되며 P1번 노선의 P2역과 Q1번 노선의 Q2역이 연결된 환승역이라는 것이다. 이미 환승역으로 주어진 역은 중복되게 주어지지 않는다.

그 다음 줄에는 사용자의 요청 개수 K(1 ≤ K ≤ 1,000)가 주어진다.

이어서 K개의 줄에 걸쳐 5개의 양의 정수 T(0 ≤ T ≤ 1,000), U1, U2, V1, V2가 주어지며, 환승에 걸리는 소요 시간이 T이며 출발지는 U1번 노선의 U2역이고 도착지는 V1번 노선의 V2역이라는 뜻이다.

각 사용자의 요청에 대하여 출발지에서 도착지로 가는 최단 시간을 한 줄에 하나씩 출력한다.