우주선 방어 (큰 입력)

적이 우주선에 침입했다. 병사들은 두 가지 장치로 우주선 안을 이동한다. 하나는 텔레포터이고, 다른 하나는 터보리프트다.

방마다 텔레포터가 하나씩 있고, 방에는 색이 하나씩 정해져 있다. 어떤 방에 있는 병사는 그 방의 텔레포터로 색이 같은 다른 방 어디로든 즉시 이동한다. 이 이동에는 시간이 걸리지 않는다.

터보리프트는 한 방에서 다른 한 방으로 병사를 옮기며, 정해진 시간이 걸린다. 터보리프트는 한 방향으로만 움직인다. 방 $a$에서 방 $b$로 병사를 옮기는 터보리프트는 방 $b$에서 방 $a$로는 병사를 옮기지 못하지만, 그 일을 하는 다른 터보리프트가 따로 있을 수는 있다. 한 터보리프트를 여러 병사가 함께 쓸 수 있고, 서로 방해하지 않는다.

병사 여러 명의 출발 방과 목적지 방이 주어진다. 각 병사가 출발 방에서 목적지 방까지 가는 데 걸리는 최소 시간을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 방의 개수 $N$이 주어진다. 방 번호는 1번부터 $N$번까지다. 다음 $N$개의 줄에는 1번 방부터 $N$번 방까지의 색이 순서대로 한 줄에 하나씩 주어진다. 각 색은 길이가 1 또는 2인 문자열이고, 알파벳 소문자 a부터 z까지와 숫자 0부터 9까지만 쓴다.

다음 줄에는 터보리프트의 개수 $M$이 주어진다. 다음 $M$개의 줄에는 각각 공백으로 구분된 세 정수 $a_i$, $b_i$, $t_i$가 주어진다. 방 $a_i$에서 방 $b_i$로 $t_i$초 만에 병사를 옮기는 터보리프트가 있다는 뜻이다.

다음 줄에는 병사의 수 $S$가 주어진다. 다음 $S$개의 줄에는 각각 두 정수 $p_j$와 $q_j$가 주어지며, 이는 병사 한 명의 출발 방과 목적지 방이다.

제한

• $1 \le T \le 10$
• $1 \le N \le 80000$
• $0 \le M \le 3000$
• $1 \le S \le 100$
• $1 \le a_i, b_i \le N$
• $0 \le t_i \le 1000$
• $1 \le p_j, q_j \le N$

각 테스트 케이스마다 먼저 Case #x: 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호다. 그다음 $S$개의 줄을 출력한다. $j$번째 줄에는 병사가 방 $p_j$에서 방 $q_j$까지 가는 데 걸리는 최소 시간을 초 단위 정수로 출력한다. 갈 수 있는 경로가 없으면 -1을 출력한다.