Dynamic Diameter 2

Description

You are given an edge-weighted tree of size $N$ where vertices are numbered from $0$ to $N-1$. The tree is rooted at vertex $0$. Vertex $i$ is connected to vertex $p_i$ with an edge of length $d_i$.

For each vertex $i$, let $l_i$ denote the length of the longest path such that vertex $\mathbf{i}$ is contained in the path and all vertices used are contained in the subtree of $i$. Recall a path is a sequence of vertices $a_1,a_2,\ldots,a_k$ such that all $a$ are distinct and $a_i$ and $a_{i+1}$ is connected by an edge. Your job is to find $\sum_{i=1}^n l_i$.

Since this problem is not hard enough to be a December Course problem 5, we are going to make $Q$ modifications to the tree. In the $i$-th modification you will be given $v_i$ and $add_i$. You should increase the edge connecting vertex $v_i$ and $p_{v_i}$ by $add_i$. Note that updates are persistent, modifications made to the tree will apply when processing futures modifications.

Also because $\sum_{i=1}^n l_i$ is very big, you should find the answer modulo $10^9+7$.

Input

The first line contains a single integer $N$, the number of vertices in the tree.

The second line contains $N-1$ integers $p_1,p_2,\ldots,p_{N-1}$.

The third line contains $N-1$ integers $d_1,d_2,\ldots,d_{N-1}$.

The fourth line contains $Q$, the number of updates.

The following $Q$ lines contains two integers $v_i$ and $add_i$.

Output

You should output $Q+1$ lines. The first line should contain the answer before any updates are made. On the $i+1^\text{th}$ line you should print the answer after the $i^\text{th}$ modification.

All answers must be printed modulo $10^9+7$.

Constraints

• $2 \leq N \leq 100~000$
• $1 \leq Q \leq 100~000$
• $1 \leq d_i \leq 100~000~000$
• $0 \leq p_i < i$
• $1 \leq v_i < N$
• $1 \leq add_i \leq 1~000~000~000$

Subtasks

• $1 \leq N \leq 1~000$, $1 \leq Q \leq 1~000$ ($11$ points)
• The height of the tree is at most $50$ ($13$ points)
• $d_i = 100~000~000$, $add_i=1$ ($31$ points)
• No additional constraints ($45$ points)

Sample Input

5
0 0 1 1
0 0 0 0
10
1 2
2 2
3 2
4 2
4 1
3 1
2 1
1 1
4 1000
2 1000

Sample Output

0
2
4
8
10
12
13
14
15
2015
3015