В новом семестре Ваня решил серьёзно взяться за учебу и перестать прогуливать пары, поэтому сейчас он торопится на пару по философии. Как известно, любое здание университета представляет собой систему из N аудиторий, пронумерованных натуральными числами от 1 до N, и M коридоров между ними. Ванин университет не исключение. Любому студенту известно, что все коридоры имеют одинаковую длину, по любому из коридоров можно ходить в любую сторону, никакой коридор не соединяет аудиторию саму с собой, никакие две аудитории не соединены больше, чем одним коридором, и что из любой аудитории можно добраться в любую, не покидая здание.

Поднявшись на шестой этаж, Ваня понял, что больше не может сделать ни шагу, не выпив перед этим кофе. К счастью, у Вани с собой есть целых K стаканчиков кофе, он точно знает, что, выпив i-й стакан, сможет пройти ровно a_i коридоров (даже если он дойдет до нужной аудитории, посетив меньше коридоров, то всё равно не сможет остановиться, пока не пройдёт a_i коридоров).

Сейчас Ваня находится в аудитории с номером 1 и ему нужно решить философский вопрос — сколько же стаканчиков кофе нужно выпить, чтобы дойти до нужной аудитории. Ваня опаздывает, поэтому он хочет выпить наименьшее число. Ещё одна проблема в том, что он точно не помнит, в какой аудитории будет проходить пара, поэтому хочет ответить на вопрос для каждой возможной аудитории независимо.

Более формально, для каждой аудитории v независимо надо найти такое наименьшее число x, что существует такое подмножество стаканчиков с индексами i₁, i₂, …, i_x, для которого найдётся путь из аудитории 1 в аудиторию v, состоящий ровно из a_i1 + a_i2 + … + a_ix коридоров. Аудитории и коридоры в пути могут использоваться более одного раза, в частности, можно пройти по какому-то коридору из аудитории a в b и затем сразу же вернуться снова в a. Если такого x не существует, то выведите вместо него −1. Сумму пустого подмножества стаканчиков можно считать равной 0.

В первой строке содержатся три целых числа N, M и K — количество аудиторий, коридоров и стаканчиков кофе соответственно (2 ≤ N ≤ 10⁵; N − 1 ≤ M ≤ 2 · 10⁵; 1 ≤ K ≤ 10⁵).

Следующие M строк содержат по два целых числа u_i и v_i — описание очередного коридора, соединяющего аудитории u_i и v_i (1 ≤ u_i, v_i ≤ N). Гарантируется, что никакой коридор не соединяет аудиторию саму с собой, что каждый коридор во входных данных встречается не более одного раза и что предоставленный план университета является связным.

Следующая строка содержит K целых чисел a₁, a₂, … , a_K — описания стаканчиков кофе Вани (1 ≤ a_i ≤ 10⁹).

В единственной строке выведите N чисел — ответ для каждой вершины.

В первом примере возможные расстояния до аудиторий 2, 3, 4, 5 равны 1, 2, 3, 4 коридоров соответственно. Для любого из этих расстояний найдётся один подходящий стаканчик.

Во втором примере до аудитории 5 можно добраться через 4 коридора, а кофе хватит максимум на 2 + 1 = 3 коридора.

В третьем примере, пройдя 999 раз по единственному коридору, Ваня в итоге окажется в аудитории 2.