색칠 터널

장난감 공장은 제품을 색이 있는 터널들 사이로 이동시켜 색을 입힙니다. 원하는 최종 색을 얻으려면 제품은 정해진 순서대로 여러 색으로 칠해져야 합니다.

각 터널은 평면 위에 놓인, 고정된 색을 가진 하나의 선분입니다. 한 가지 색을 내는 터널이 여러 개일 수 있고, 서로 다른 터널이 같은 색을 가질 수도 있습니다. 어떤 색으로 칠해지려면 제품은 그 색 터널의 한 끝점에서 반대쪽 끝점까지 통과(완전히 지나가기)해야 하며, 통과 방향은 상관없습니다.

엄밀히 말하면, 칠해지지 않은 제품이 주어진 출발점에서 시작하여, 색 $c_1, c_2, \ldots, c_n$ 순서로 칠해진 뒤 주어진 도착점까지 이동해야 합니다. 따라서 제품은 터널 $t_1, t_2, \ldots, t_n$ 을 이 순서대로 통과해야 하며, 이때 터널 $t_i$ 의 색은 $c_i$ 입니다. 도중에 다른 터널을 지나가거나 가로질러도 되며, 색 조건을 만족해야 하는 것은 선택한 부분수열 $t_1, \ldots, t_n$ 뿐입니다. 통과와 통과 사이에 제품은 장애물이 없는 평면 위를 직선 구간으로 이동합니다. 경로는 스스로 교차하거나 터널을 통과하지 않고 단순히 가로지를 수 있으며(이 경우 칠해지지 않습니다), 같은 터널을 두 번 이상 통과해도 됩니다.

출발점에서 도착점까지 이러한 조건을 만족하는 가장 짧은 경로의 길이를 구하세요.

첫째 줄에 테스트 케이스의 수를 나타내는 정수 $t$ ($1 \le t \le 20$) 가 주어집니다. 각 테스트 케이스는 다음과 같이 주어집니다.

• 첫 줄: 네 실수 $x_s\ y_s\ x_t\ y_t$. 출발점 $(x_s, y_s)$ 와 도착점 $(x_t, y_t)$ 의 좌표입니다.
• 둘째 줄: 색 수열. 먼저 그 길이를 나타내는 정수 $m$ ($1 \le m \le 30$) 이 오고, 이어서 $m$ 개의 정수 $c_1, \ldots, c_m$ (각각 $[1, 100]$) 이 순서대로 주어집니다.
• 셋째 줄: 터널의 개수를 나타내는 정수 $n$ ($1 \le n \le 60$).
• 이후 $n$ 개의 줄: 각 줄에 다섯 개의 수 $x_1\ y_1\ x_2\ y_2\ c$ 가 주어집니다. 한 터널의 두 끝점 $(x_1, y_1)$, $(x_2, y_2)$ (실수) 와 색 $c$ (정수, $[1, 100]$) 입니다.

수열에 등장하는 모든 색은 적어도 하나의 터널로 만들 수 있으므로, 유효한 경로는 항상 존재합니다.

각 테스트 케이스마다 한 줄에, 요구된 색 순서대로 터널을 통과하면서 출발점에서 도착점까지 이동하는 최소 총 길이를 소수점 아래 셋째 자리까지 정확히 반올림하여 출력하세요.