“几乎清洁的资金树”（简称 ACM 树）由 $N$（$1 \le N \le 500\,000$）个节点组成，在这些节点上，（几乎清洁的）资金正在生长（这与“钱不会从树上长出来”的古老俗语相反）。节点编号为 $0$ 到 $N-1$，其中节点 $0$ 是树的根。除节点 $0$ 外，每个节点 $i$ 在树中都有一个父节点 $p(i)$，满足 $p(i) < i$。最初，每个节点包含 $v(i)$（$0 \le v(i) < 1\,000\,000\,007$）个货币单位。由于其特殊的性质，这棵树吸引了一个大型洗钱组织的注意，他们希望利用这棵树进行其资金“清洗”业务。该组织希望在树上执行 $Q$（$1 \le Q \le 50\,000$）次操作。每次操作由两个步骤组成：

1. 在步骤 1 中，从树中选择 $K$（$1 \le K \le 1\,000$）个节点：$x(1), \dots, x(K)$（$0 \le x(i) \le N-1$）——同一个节点可能会被多次选中。在这些节点中的每一个，都会增加一定数量的货币单位（从而增加其中的货币单位数量）。更具体地说，向选定的节点 $x(i)$（$1 \le i \le K$）增加 $y(i)$（$0 \le y(i) < 1\,000\,000\,007$）个货币单位。
2. 在步骤 2 中，选择两个节点 $u$ 和 $v$（$0 \le u, v \le N-1$），该组织希望知道位于树中节点 $u$ 和 $v$ 之间的唯一路径上的所有节点（包括 $u$ 和 $v$）中所包含的货币单位总数。

该组织雇佣你来寻找这 $Q$ 次操作中每一次操作步骤 2 的答案，并承诺如果你成功，将给你一笔丰厚的报酬。

输入格式

输入的第一行包含树的节点数 $N$。

接下来的 $N-1$ 行，每行包含两个空格分隔的整数 $p(i)$ 和 $i$，描述树的一条边。

下一行包含 $N$ 个空格分隔的值：每个节点中初始的货币单位数量 $v(0), \dots, v(N-1)$。

下一行包含操作次数 $Q$。

接下来的 $Q$ 行，每行描述一个操作。每个操作由 9 个空格分隔的整数按以下顺序描述：$K, x(1), y(1), A, B, C, D, u, v$（$0 \le A, B, C, D < 1\,000\,000\,007$）。值 $x(i)$（$2 \le i \le K$）和 $y(i)$（$2 \le i \le K$）按如下方式生成：

$$x(i) = (A \cdot x(i-1) + B) \bmod N$$ $$y(i) = (C \cdot y(i-1) + D) \bmod 1\,000\,000\,007$$

输出格式

对于每个 $Q$ 操作，输出一行，包含该操作步骤 2 的答案。在计算某个操作的答案时，也需要考虑之前操作中步骤 1 的影响（即，在向节点 $x(i)$ 增加 $y(i)$ 个货币单位后，这些单位在执行后续操作时仍会保留在节点中）。

样例

输入样例 1

4
0 1
0 3
1 2
1 2 3 4
3
1000 1 1 1 0 1 0 0 2
2 0 5 1 1 2 2 2 3
1 3 7 999 999 999 999 1 3

输出样例 1

1006
1027
1031

说明

在第一次操作中，数值 $1$ 被向节点 $1$ 累加了 $1000$ 次（注意 $A=C=1, B=D=0$）。节点 $0$ 和 $2$ 之间的路径包含节点 $0, 1$ 和 $2$。它们中的货币单位总数为 $1006$。

在第二次操作中：$x(1)=0, y(1)=5, x(2)=1, y(2)=12$。节点 $2$ 和 $3$ 之间的路径包含树的所有节点。

在第三次操作中：$K=1$，因此 $A, B, C, D$ 是无关紧要的。