In the new semester, Vanya decided to seriously focus on his studies and stop skipping classes, so he is now rushing to his philosophy class. As is known, any university building consists of a system of N classrooms, numbered with natural numbers from 1 to N, and M corridors between them. Vanya’s university is no exception. Every student knows that all corridors have the same length, you can walk in either direction along any corridor, no corridor connects a classroom to itself, no two classrooms are connected by more than one corridor, and it is possible to reach any classroom from any other without leaving the building.

After reaching the sixth floor, Vanya realized that he could not take another step without having coffee first. Fortunately, Vanya has K cups of coffee with him, and he knows that after drinking the i-th cup, he will be able to walk exactly a_i corridors (even if he reaches the desired classroom by passing fewer corridors, he still cannot stop until he has walked a_i corridors).

Currently, Vanya is in classroom number 1 and needs to solve the philosophical question — how many cups of coffee does he need to drink to reach the desired classroom? Vanya is running late, so he wants to drink the smallest number possible. Another problem is that he does not exactly remember which classroom the class will be held in, so he wants to answer the question for each possible classroom independently.

More formally, for each classroom v, he needs to find the smallest number x such that there exists a subset of cups with indices i₁, i₂, …, i_x, for which there is a path from classroom 1 to classroom v consisting of exactly a_i1 + a_i2 + … + a_ix corridors. Classrooms and corridors in the path can be used more than once; in particular, it is possible to walk through a corridor from classroom a to b and then immediately return to a. If such an x does not exist, output −1 instead. The sum of an empty subset of cups can be considered equal to 0.

The first line contains three integers N, M, and K — the number of classrooms, corridors, and cups of coffee, respectively (2 ≤ N ≤ 10⁵; N − 1 ≤ M ≤ 2 · 10⁵; 1 ≤ K ≤ 10⁵).

The next M lines contain two integers u_i and v_i — the description of the next corridor connecting classrooms u_i and v_i (1 ≤ u_i, v_i ≤ N). It is guaranteed that no corridor connects a classroom to itself, that each corridor appears in the input no more than once, and that the provided university layout is connected.

The next line contains K integers a₁, a₂, … , a_K — the descriptions of Vanya’s cups of coffee (1 ≤ a_i ≤ 10⁹).

In a single line, output N numbers — the answer for each classroom.

In the first example, the possible distances to classrooms 2, 3, 4, 5 are 1, 2, 3, 4 corridors, respectively. For any of these distances, there is one suitable cup.

In the second example, classroom 5 can be reached through 4 corridors, but the coffee is enough for a maximum of 2 + 1 = 3 corridors.

In the third example, after walking 999 times through the only corridor, Vanya will end up in classroom 2.