여행 (스몰)

첼시가 사는 주에는 도시가 $N$개 있고 1번부터 번호가 붙어 있다. 첼시는 1번 도시에 산다. 도시를 직접 잇는 양방향 도로가 $M$개 있으며, 같은 두 도시를 잇는 도로가 여러 개일 수도 있다. 시간대마다 교통 상황이 달라져서 같은 도로라도 출발하는 시각에 따라 지나는 데 걸리는 시간이 다르다. 이동 방향은 상관없다. 어느 쪽으로 가든 막히는 정도가 같기 때문이다.

도로를 지나는 이동은 언제나 정각에 시작해 정각에 끝난다. 한 도로를 다 지난 순간 곧바로 다음 도로로 출발할 수 있다.

첼시는 겨울 휴가를 어디로 갈지 고르고 있다. 목적지와 출발 시각을 여러 가지로 바꿔 가며 자기 도시에서 목적지까지 가는 데 최소 몇 시간이 걸리는지 알고 싶어 한다. 가는 길에 다른 도시를 거쳐도 된다. 첼시의 질문에 모두 답하라.

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

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

이어서 $2M$개의 줄, 곧 두 줄씩 묶인 $M$개의 쌍이 주어진다. 각 쌍의 첫째 줄에는 서로 다른 두 정수 $x$와 $y$가 주어지고, $x$번 도시와 $y$번 도시를 잇는 양방향 도로 하나를 나타낸다. 둘째 줄에는 정수 24개 $Cost[t]$ ($0 \le t \le 23$)가 주어진다. $Cost[t]$는 그 도로를 $t$시 정각에 출발해 지날 때 걸리는 시간이며 단위는 시간이다. $0 \le t \le 22$인 모든 $t$에서 $Cost[t] \le Cost[t+1] + 1$이고, $Cost[23] \le Cost[0] + 1$임이 보장된다.

이어서 $K$개의 줄이 주어진다. 각 줄에는 정수 $D$와 $S$가 주어지며, 첼시가 1번 도시를 $S$시 정각에 떠나 $D$번 도시까지 갈 때 최소 몇 시간이 걸리는지 묻는 질문이다.

제한

• $1 \le T \le 100$
• $2 \le N \le 20$
• $1 \le M \le 100$
• $1 \le K \le 100$
• $1 \le x, y \le N$이고 $x \ne y$
• $1 \le Cost[t] \le 50$
• $1 \le D \le N$
• $0 \le S \le 23$

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