题目描述

给你一棵 $n$ 个节点的树，节点标号从 $1$ 到 $n$。每个节点上有一个整数权值 $a_i$。然后再给你两个整数 $L,R$。

你需要进行 $m$ 次如下操作：

• 给定树上两个节点 $u,v$ 和一个整数 $d$，将树上 $u$ 到 $v$ 的路径上所有点权加 $d$。

在每个操作后，你需要输出以下问题的答案：

• 所有节点个数在 $[L,R]$ 范围内的简单路径的权值和之和。

由于答案可能很大，你只需要输出答案对 $P=10^9+7$ 的余数即可。

输入格式

输入的第一行包含四个正整数 $n,m,L,R$，分别表示节点个数、操作个数和两个参数。

第二行包含 $n$ 个整数，表示树上每个节点的初始权值。

第三行包含 $n-1$ 个整数，描述树的形态，其中第 $i$ 个数 $f_i$ 表示节点 $i+1$ 与节点 $f_i$ 之间有一条边。

接下来 $m$ 行，第 $i$ 行包含三个整数 $u_i,v_i,d_i$，描述题目中的第 $i$ 次操作。

输出格式

输出 $m$ 行，每行一个整数，第 $i$ 行的整数表示对于第 $i$ 个操作后的答案。

样例输入

10 10 3 6
36 11 76 24 71 89 24 63 75 40
1 1 2 2 3 3 4 4 5
2 5 18
5 7 95
7 10 82
8 2 99
8 1 85
7 7 60
1 5 85
4 3 38
9 4 17
1 1 99

样例输出

7591
17186
26124
32163
39473
39953
46073
49835
50328
52803

数据范围

对于所有数据，保证：

• $1\le n,m\le10^5$
• $1\le L\le R\le n$
• $0\le a_i<P$
• $1\le f_i\le i<n$
• $1\le u_i,v_i\le n$
• $0\le d<P$

特殊性质 A： $f_i=i$。

特殊性质 B： $f_i=\left\lfloor\frac{i+1}{2}\right\rfloor$。

特殊性质 C： 相同的 $f_i$ 最多出现 $2$ 次。