Travel (Large)

Chelsea's state has N cities, numbered from 1. Chelsea lives in city 1. M two-way roads join pairs of cities directly, and one pair may be joined by more than one road.

Traffic changes during the day, so the time a road takes depends on the hour the trip on it starts. The direction does not matter, because traffic is equally bad both ways. Every trip on a road starts and ends exactly on the hour, and a trip on one road may start the moment a trip on another road ends.

Chelsea is picking a place for her winter holiday. Each of her questions names a destination city and the hour she leaves city 1, and she wants the fewest hours the journey takes. The route may pass through other cities on the way. Answer all of her questions.

The first line contains the number of test cases T. T test cases follow.

The first line of each test case contains three integers: the number of cities N, the number of roads M, and the number of questions K.

Then come $2M$ lines, that is M pairs of two lines. In each pair, the first line contains two different integers $x$ and $y$, describing one two-way road between city $x$ and city $y$. The second line contains 24 integers $\text{Cost}[t]$ ($0 \le t \le 23$), where $\text{Cost}[t]$ is the number of hours the road takes when the trip on it starts at $t$ o'clock. It is guaranteed that $\text{Cost}[t] \le \text{Cost}[t+1] + 1$ for $0 \le t \le 22$, and that $\text{Cost}[23] \le \text{Cost}[0] + 1$.

K lines follow. Each contains two integers D and S, forming one question: how few hours does it take to get from city 1 to city D when Chelsea leaves city 1 at S o'clock?

Limits

• $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$ and $x \ne y$
• $1 \le \text{Cost}[t] \le 50$
• $1 \le D \le N$
• $0 \le S \le 23$

For each test case, print one line containing Case #x: , where $x$ is the test case number starting from 1, followed by K space separated integers: the answers to the questions, in the order they were asked. If no route takes Chelsea to the destination city of a question, print -1 for that question.