法师 Roxanne 在研究了无数个小时的古代奥术后，决定去当地的一家咖啡馆放松一下。当她到达那家老咖啡馆时，她看到墙上有一种奇怪的结构，称为 arboras（即树）。形式上，它是一个包含 $N$ 个顶点的集合，顶点编号为从 $0$ 开始的连续非负整数，其中顶点 $0$ 是根，所有其他顶点都有一个唯一的父节点（顶点 $v$ 的父节点为 $p_v$）。由于这家咖啡馆是由法师和程序员共同经营的，所以这棵树被绘制成根在顶部的形式。

法师对这种结构很感兴趣，她决定将一些魔法咖啡倒入其中一个顶点。如果咖啡被倒入顶点 $u$，它就会向下流动，穿过以 $u$ 为根的子树。由于这是魔法咖啡，它不会随机流动：它会占据以 $u$ 为根的子树中，且经过顶点 $u$ 的最长链。倒入咖啡时损失的咖啡量与咖啡所占据的链的长度成正比。Roxanne 将此量记为 $r_u$。注意，树中各条边的长度可能不同。

Roxanne 对如果她将咖啡倒入树中所有顶点所损失的咖啡总量感兴趣，即树中所有顶点 $u$ 的 $r_u$ 之和。起初计算这个并不困难，但随后程序员们决定挑战她，并 $Q$ 次增加了某些边的长度。你能帮助 Roxanne 计算出在初始状态以及每次 $Q$ 次更新后，如果将咖啡倒入所有顶点，咖啡所占据的所有链的总长度吗？注意：她需要的结果是对 $10^9 + 7$ 取模后的值。

输入格式

第一行包含整数 $N$，即顶点数量。 第二行包含 $N - 1$ 个整数：$p_1, p_2, \dots, p_{N-1}$，其中 $p_v$ 是顶点 $v$ 的父节点，顶点 $0$ 是根。 第三行包含 $N - 1$ 个整数：$d_1, d_2, \dots, d_{N-1}$，其中 $d_v$ 是顶点 $v$ 与其父节点 $p_v$ 之间边的长度。 第四行包含 $Q$，即更新次数。 接下来的 $Q$ 行，每行包含两个整数 $v_i$ 和 $add_i$，表示第 $i$ 次更新：顶点 $v_i$ 与其父节点 $p_{v_i}$ 之间边的长度增加了 $add_i$。

输出格式

输出 $Q + 1$ 行：第 $i + 1$ 行应输出第 $i$ 次更新后的答案。第一行应输出更新前的答案。 所有答案必须对 $10^9 + 7$ 取模。

数据范围

• $1 \le N \le 100\,000$
• $1 \le Q \le 100\,000$
• 对于所有 $1 \le i \le N - 1$，$1 \le d_i \le 100\,000\,000$
• $0 \le p_i < i$
• 对于所有 $1 \le i \le Q$，$1 \le add_i \le 10^9$

子任务

子任务 1（11 分）： $1 \le N \le 1\,000$ $1 \le Q \le 1\,000$

子任务 2（13 分）： * 树的高度最多为 $50$。

子任务 3（31 分）： 对于所有 $1 \le i \le N - 1$，$d_i = 100\,000\,000$ 对于所有 $1 \le i \le Q$，$add_i = 1$

子任务 4（45 分）： * 无附加限制。

样例

样例输入 1

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

样例输出 1

0
2
4
8
10
12
13
14
15
2015
3015