Now Matt is preparing for the Graduate Record Examinations as Coach Pang did in 2013 and George did in 2011.

Thanks to modern techniques, Matt uses automata instead of old-fasioned vocabulary books.

The automata used by Matt is a directed acyclic graph (DAG) with N vertices and M edges. The vertices are conveniently numbered by 1, 2, . . . , N . Each edge is labeled with an integer. Additionally, some vertices are marked as special.

A GRE word is obtained by concatenating the labels on the path from vertex 1 to a special vertex.

Now, Matt has Q questions. The i-th question is asking for the length of ki-th smallest words among all the GRE words he can obtain in lexicographical order.

The first line contains only one integer T , which indicates the number of test cases.

For each test case, the first line contains three integers N, M, Q (2 ≤ N ≤ 10⁵, 0 ≤ M ≤ 10⁵, 1 ≤ Q ≤ 10⁵).

The second line contains N - 1 integers s₂, . . . , s_n. If the i-th vertex is special, then s_i = 1. Otherwise, s_i = 0. Vertex 1 is never special.

Each of the following M lines contains three integers a_i, b_i, c_i denoting an edge from vertex ai to vertex b_i labeled with c_i (1 ≤ a_i, b_i ≤ N, 1 ≤ c_i ≤ 10⁹). For each vertex v, all outgoing edges are labeled with distinct integers.

Each of the following Q lines contains the integer ki (1 ≤ k_i ≤ 10⁸) of the i-th question.

For each test case, output “Case #x:” in the frirst line, where x is the case number (starting from 1).

Then, for each question, output the length of the word in one line. If the word does not exist, output “-1” (without quotes) instead.

1
3 3 4
1 1
1 2 1
1 3 12
2 3 3
1
2
3
4

Case #1:
1
2
1
-1

2014ACM/ICPC亚洲区北京站-重现赛（感谢北师和上交）