여행 (큰 입력)

첼시가 사는 주에는 도시가 N개 있고 1번부터 번호가 붙어 있다. 첼시는 1번 도시에 산다. 두 도시를 직접 잇는 양방향 도로는 M개이며, 같은 도시 쌍을 잇는 도로가 둘 이상일 수도 있다.

교통량은 하루 동안 달라지므로, 도로 하나를 지나는 데 걸리는 시간은 그 도로에 들어서는 시각에 따라 달라진다. 진행 방향은 상관없다. 어느 쪽으로 가든 막히는 정도가 같기 때문이다. 도로 통행은 언제나 정각에 시작해 정각에 끝나고, 한 도로의 통행이 끝난 즉시 다른 도로의 통행을 시작할 수 있다.

첼시는 겨울 휴가를 어디로 갈지 고르고 있다. 질문마다 목적지 도시와 1번 도시를 떠나는 시각이 정해져 있고, 그때 걸리는 최소 시간을 알고 싶어 한다. 가는 길에 다른 도시를 거쳐도 된다. 첼시의 질문에 모두 답하라.

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

각 테스트 케이스의 첫 줄에는 정수 세 개가 주어진다. 도시의 수 N, 도로의 수 M, 질문의 수 K이다.

이어서 $2M$개의 줄, 곧 두 줄씩 M쌍이 주어진다. 각 쌍의 첫 줄에는 서로 다른 두 정수 $x$와 $y$가 주어지며, $x$번 도시와 $y$번 도시를 잇는 양방향 도로 하나를 뜻한다. 둘째 줄에는 정수 24개 $\text{Cost}[t]$ ($0 \le t \le 23$)가 주어진다. $\text{Cost}[t]$는 그 도로에 $t$시 정각에 들어섰을 때 지나는 데 걸리는 시간이고, 단위는 시간이다. $0 \le t \le 22$에 대해 $\text{Cost}[t] \le \text{Cost}[t+1] + 1$이고 $\text{Cost}[23] \le \text{Cost}[0] + 1$임이 보장된다.

이어서 K개의 줄이 주어진다. 각 줄에는 정수 두 개 D와 S가 주어지며 질문 하나를 이룬다. 첼시가 1번 도시를 S시 정각에 떠날 때 D번 도시까지 가는 데 걸리는 최소 시간은 몇 시간인가?

제한

• $1 \le T \le 5$
• $2 \le N \le 500$
• $1 \le M \le 2000$
• $1 \le K \le 5000$
• $1 \le x, y \le N$이고 $x \ne y$
• $1 \le \text{Cost}[t] \le 50$
• $1 \le D \le N$
• $0 \le S \le 23$

각 테스트 케이스마다 한 줄에 Case #x: 를 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이다. 그 뒤에 질문의 답 K개를 물어본 순서대로 공백으로 구분해 출력한다. 어떤 경로로도 그 질문의 목적지 도시에 갈 수 없다면 그 질문의 답으로 -1을 출력한다.