You are given a rooted tree with ~N~ nodes numbered from ~0~ to ~N - 1~, where node ~0~ is the root. The tree has ~N - 1~ edges, and for each node ~i~ (where ~1 \le i \le N - 1~), there is an edge of length ~d_i~ connecting it to its parent ~p_i~.

Define ~f(i)~ as the length of the longest simple path in the subtree rooted at node ~i~ that passes through node ~i~.

Your task is to compute the sum of ~f(i)~ for all nodes modulo ~10^9+7~, i.e. ~\left( \sum_{i = 0}^{N - 1} f(i) \right) \mod{10^9+7}~.

Moreover, there are ~Q~ updates. In each update, you are given two integers ~i~ and ~x~, meaning the edge between node ~i~ and its parent ~p_i~ increases its length by x. After each update, output the new sum modulo ~10^9+7~.

Input Specification

The first line contains an integer ~N~ (~1 \le N \le 10^5~), the number of nodes.

The second line contains ~N - 1~ integers ~p_1~, ~p_2~, ~\ldots~, ~p_{N - 1}~, (~0 \le p_i < i~), the parent of each node ~i~ (for ~1 \le i \le N - 1~).

The second line contains ~N - 1~ integers ~d_1~, ~d_2~, ~\ldots~, ~d_{N - 1}~, (~0 \le d_i \le 10^9~), the initial edge length between node ~i~ and ~p_i~.

The fourth line contains an integer ~Q~ (~1 \le Q \le 10^5~), the number of update operations.

The next ~Q~ lines each contain two integers ~i~ and ~x~, (~1 \le i \le N-1~, ~1 \le x \le 10^9~), representing an update: increase the weight of the edge between ~i~ and ~p_i~ by ~x~.

Output Specification

Output ~Q+1~ lines. The first line should contain the initial sum of ~f(i)~ modulo ~10^9+7~, and then print ~Q~ lines, each with the new sum modulo ~10^9+7~ after the corresponding update.

Constraints

Subtask	Points	Additional constraints
~1~	~15~	~N, Q \le 1\,000~
~2~	~15~	Tree's height is at most ~50~.
~3~	~30~	All ~d_i~ are the same, and ~x=1~ for all updates.
~4~	~40~	No additional constraints

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

Explanation for Sample

Initial tree:

      0
     / \
    1   2
   / \
  3   4

• Initially, ~f(i) = 0~.
• After the first update, ~f(0) = 2~. The sum is ~2~.
• After the second update, ~f(0) = 4~. The sum is ~4~.
• After the third update, ~f(0) = 6~ and ~f(1) = 2~. The sum is ~8~.
• After the fourth update, ~f(0) = 6~ and ~f(1) = 4~. The sum is ~10~.