Travel (Small)

Chelsea's state has $N$ cities, numbered from 1, and Chelsea lives in city 1. $M$ bidirectional roads connect them directly, and one pair of cities may be joined by more than one road. Traffic changes over the course of a day, so the time a road takes depends on the hour the trip starts. The direction of travel makes no difference, because traffic is equally bad both ways.

Every trip on a road starts on the hour and ends on the hour. Chelsea may start a trip on the next road the moment she finishes the previous one.

Chelsea is deciding where to go for her winter holiday. For several destinations and several departure hours she wants to know the fewest hours the journey from her own city can take. 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. The first line of a pair contains two different integers $x$ and $y$ describing one bidirectional road between city $x$ and city $y$. The second line contains 24 integers $Cost[t]$ ($0 \le t \le 23$), where $Cost[t]$ is the time in hours the road takes when the trip starts at $t$ o'clock. It is guaranteed that $Cost[t] \le Cost[t+1] + 1$ for $0 \le t \le 22$, and that $Cost[23] \le Cost[0] + 1$.

Then come $K$ more lines. Each contains two integers $D$ and $S$ that make up one question: how few hours does it take to travel from city 1 to city $D$ if Chelsea leaves city 1 at $S$ o'clock?

Limits

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

For each test case, print one line beginning with Case #x:, where x is the test case number starting from 1. After it print the $K$ answers in order, separated by single spaces. If Chelsea cannot reach the destination of a question no matter which roads she takes, print -1 for that question.