여행

Chelsea의 주에는 N개의 도시가 있으며(Chelsea의 도시인 1부터 번호가 매겨진다), M개의 양방향 도로가 이 도시들을 직접 연결한다. (한 쌍의 도시가 둘 이상의 도로로 직접 연결되어 있을 수도 있다.) 교통 양상의 변화로 인해, 이동을 시작하는 시각에 따라 하루 중 서로 다른 시각에 같은 도로를 이용하는 데 걸리는 시간이 다를 수 있다. (하지만 도로에서 이동하는 방향은 중요하지 않다. 교통 상황은 항상 양방향에서 똑같이 나쁘다!) 도로에서의 모든 이동은 정시에 시작하고 정시에 끝나며, 한 도로에서의 이동을 마친 즉시 다른 도로에서의 이동을 시작할 수 있다.

Chelsea는 여행을 좋아하며 겨울 휴가 여행으로 어디에 갈지 정하고 있다. 그녀는 자신의 도시를 출발하는 시각에 따라 자신의 도시에서 여러 다른 목적지 도시까지 얼마나 빨리 갈 수 있는지 궁금해한다. (목적지로 가는 경로에는 도중에 다른 중간 도시들이 포함될 수 있다.) 그녀의 모든 질문에 답할 수 있는가?

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ x, y ≤ N. 1 ≤ 모든 Cost 값 ≤ 50. 1 ≤ D ≤ N. 0 ≤ S ≤ 23.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ T ≤ 100. 2 ≤ N ≤ 20. 1 ≤ M ≤ 100. 1 ≤ K ≤ 100.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ T ≤ 5. 2 ≤ N ≤ 500. 1 ≤ M ≤ 2000. 1 ≤ K ≤ 5000.

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

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

이어서 2M개의 줄, 즉 각각 두 줄로 이루어진 M개의 쌍이 주어진다. 각 쌍의 첫 줄에는 x번째 도시와 y번째 도시 사이의 양방향 도로 하나를 나타내는 서로 다른 두 정수 x와 y가 주어진다. 둘째 줄에는 그 도로에서 t시에 출발할 때 도로를 이용하는 데 드는 시간 비용을 시간 단위로 나타내는 24개의 정수 Cost[t] (0 ≤ t ≤ 23)가 주어진다. Cost[t] ≤ Cost[t+1]+1 (0 ≤ t ≤ 22)이고 Cost[23] ≤ Cost[0]+1임이 보장된다.

그다음 추가로 K개의 줄이 주어진다. 각 줄에는 하나의 질문을 구성하는 두 정수 D와 S가 주어진다. 그 질문은 Chelsea가 1번 도시에서 S시에 출발할 경우 1번 도시에서 D번 도시까지 가는 데 걸리는 최소 시간이 몇 시간인지 묻는다.

각 테스트 케이스마다 "Case #x: "를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이며, 그 뒤에 질문의 답인 서로 다른 K개의 정수를 질문 순서대로 공백으로 구분하여 출력한다. 어떤 도로를 택하더라도 Chelsea가 질문의 목적지 도시에 도달할 수 없다면, 그 질문에 대해 -1을 출력한다.