O. В бухгалтерии опять всё перепутали

В компании $n$ сотрудников; сотрудник $0$ — директор, у каждого остального есть ровно один непосредственный начальник. Множество сотрудника $v$ — это он сам, все его начальники (вплоть до директора) и все его подчинённые (всё поддерево).

В нулевой день сотруднику $i$ платят $c_i$. Далее $m$ дней; в день $i$ даны два номера $a_i$ и $b_i$:

1. считается $s_i$ — сумма зарплат по множеству сотрудника $a_i$, взятая по модулю $10^9 + 7$;
2. затем $s_i$ прибавляется к зарплате каждого сотрудника из множества сотрудника $b_i$.

Выведите зарплату сотрудника $n - 1$ в каждый из дней с нулевого по $m$-й. Она не берётся по модулю.

В первой строке — числа $n$ и $m$ ($1 \le n, m \le 10^5$). Во второй — $n - 1$ число: начальники сотрудников $1, \ldots, n - 1$. В третьей — $n$ чисел $c_i$ ($1 \le c_i \le 10^9$). В следующих $m$ строках — пары $a_i$, $b_i$ ($0 \le a_i, b_i \le n - 1$).

В единственной строке выведите $m + 1$ число — зарплату сотрудника $n - 1$ в дни с нулевого по $m$-й.