Задача 2A. Авторитеты ≡

Условие

На экзамен по информатике пришло n участников, пронумерованных от 1 до n. Среди участников некоторые участники были друзьями, а точнее одни участники были авторитетами для других участников. Для i-го участника известны номера участников, которые являются его авторитетами.

Каждый участник экзамена определил условия, когда он точно завершит свой экзамен. Таким образом, i-й участник покинет пункт проведения экзамена в тот момент времени, который произойдет раньше:

1. С начала олимпиады прошло t_i минут.
2. Некоторые авторитеты участника завершили экзамен, и в кабинете осталось не больше c_i авторитетов.

Так как экзамен по информатике проводится с использованием компьютерных технологий, то участники олимпиады будут мгновенно завершать выполнение экзамена, если количество авторитетов в аудитории осталось не больше c_i человек.

Для каждого участника сообщите, через какое время после начала экзамена он его завершит.

Формат входных данных

В первой строке вводится натуральное число n — количество участников экзамена (1 ≤ n ≤ 10⁵).

В следующих n строках вводятся данные в следующем формате: первое число i-й строки — количество авторитетов i-го участника (обозначим за m_i), остальные m_i чисел — номера участников, которые являются авторитетами для i-го участника (0 ≤ m_i < n). Участники экзамена не очень сильно знают друг друга, поэтому сумма всех m_i не превосходит 2 * 10⁵.

В следующей строке вводится последовательность натуральных чисел t₁, t₂, ..., t_n (1 ≤ t_i ≤ 10⁹).

В последней строке вводится последовательность целых чисел c₁, c₂, ..., c_n ( − 1 ≤ c_i < m_i). Если c_i =  − 1, то i-й участник будет выполнять задания, не обращая внимания на своих авторитетов.

Формат выходных данных

Выведите n чисел, где i число означает количество минут, через которое i-й участник завершит выполнение экзамена.

Примеры тестов

5
0
1 3
1 1
0
1 4
8 5 3 8 2
-1 0 0 -1 0

8 3 3 8 2