Дракон полагал, что не все курсы и тренинги так уж полезны. Вот что ему казалось полезным почти наверняка — это занятия спортом. Правда, не тем, который с приставкой «кибер». Ему доводилось наблюдать, как затягивает игра. И хотя он был согласен, что это интересное занятие, по его мнению, это отнимает слишком много времени.
Тут Дракон поймал себя на мысли, что общение с Принцем не проходит бесследно — казалось бы, какая разница Дракону, существующему вне времени, сколько времени будет потрачено кем бы то ни было на игру...
Однажды он наблюдал за одним рыцарем, любителем играть. Он даже организовал целый клуб любителей игры. Сначала в этом клубе было n участников.
Когда этот рыцарь собирался играть, то он выбирал тип партии и отправлял сообщения своим знакомым из клуба с приглашением поиграть. Эти знакомые пересылали сообщения своим знакомым, и информация о предстоящей игре распространялась среди членов клуба.
Тип партии, помимо прочего, определяет и длительность игры. Нужно сказать, что каждый из членов клуба имел своё мнение относительно того, сколько времени можно потратить на партию. Поэтому, если члену клуба приходило сообщение, в котором предлагалось играть более долгую партию, чем считал бы возможным этот член клуба, он навсегда удалял себя из списка рассылки и не рассылал информацию о предстоящей партии своим знакомым. Те же, кого это время устраивало, принимали участие в игре.
Дракона заинтересовало, сколько же человеко-минут было потрачено на каждую игру, предложенную рыцарем. Ваша задача — определить это.
В первой строке содержатся целые числа n, m, p (2 ≤ n ≤ 105, 1 ≤ m ≤ 2·105, 1 ≤ p ≤ 2·105) — начальное количество членов клуба, количество пар участников, знакомых между собой, и количество игр, предложенных рыцарем.
Во второй строке содержится n - 1 целое число t2, t3, ..., tn (1 ≤ tj ≤ 109) — время, которое участник с соответствующим номером готов потратить на партию. Нумерация участников ведётся с единицы, при этом номер 1 имеет рыцарь, и он готов потратить на партию любое время.
В третьей строке содержится p целых чисел g1, g2, ..., gp (1 ≤ gk ≤ 109) — длительности игр в том порядке, в котором их предлагал рыцарь.
В каждой из следующих m строк записано по два целых числа — номера членов клуба, которые могут обменяться сообщениями между собой.
Выведите p целых чисел s1, s2, ..., sp, где sk — количество времени, потраченное всеми игроками на игру #k.
4 4 4
2 3 3
1 3 4 1
1 2
1 3
3 4
2 4
4 9 4 1
4 3 1
1 10 3
3
1 2
2 3
1 4
6
Поясним приведённые примеры.
В первом примере происходит следующее. В первой игре участвуют все члены клуба, поэтому суммарное потраченное на эту игру время равно 4.
Получив предложение участвовать во второй игре член клуба с номером 2 покидает клуб, и во второй игре участвуют трое игроков. Суммарное потраченное на игру время равно 9.
Перед третьей игрой клуб покидают члены с номерами 3 и 4, и в игре участвует только сам рыцарь; суммарное потраченное время равно 4. В четвёртую игру рыцарь также играет в одиночку: он остался единственным членом клуба. Потраченное на четвёртую игру время составляет 1.
Во втором примере член клуба с номером 2 отказывается от участия уже в первой игре; при этом он не пересылает сообщение о начале игры члену клуба с номером 3. Поскольку для члена клуба с номером 3 это был единственный способ узнать о предстоящей игре, то узнать о ней он уже не сможет. Таким образом, в игре примут участие два человека, а суммарное потраченное время равно 6.
| V (XVI) открытый командный студенческий чемпионат Поволжья по спортивному программированию |
|---|
| Закончено |
