时间限制： 2.0 秒

空间限制： 512 MB

题目描述

Charlie 有一棵 $n$ 节点的有根树，根节点编号为 $1$，每个节点 $i$ 有三个权值 $a_i,b_i,c_i$，现在定义对于权值的操作 $O$ 如下：

• $O=1$，令 $a_i=a_i+b_i+c_i$；
• $O=2$，令 $b_i=a_i+b_i+c_i$；
• $O=3$，令 $c_i=a_i+b_i+c_i$；
• $O=4$，给定 $v$，令 $a_i=a_i\times v$；
• $O=5$，给定 $v$，令 $b_i=b_i+v$；
• $O=6$，给定 $v$，令 $c_i=v$；
• $O=7$，表示询问操作。

定义在以上操作在树上对应节点的操作 $P$ 如下：

• $P=1$，给定 $x$，对应编号为 $x$ 的节点；
• $P=2$，给定 $x$，对应编号为 $x$ 的节点为根的子树；
• $P=3$，给定 $u,v$，对应树上 $u,v$ 两点之间的简单路径上的所有节点。

由 $O,P$ 两种操作按顺序组成一个操作，先输入 $O$ 操作，再输入 $P$ 操作。例如 1 2 3 表示对以节点 $3$ 为根的子树，子树中所有节点的 $a_i=a_i+b_i+c_i$，6 2 3 1 4 则表示树上 $1,4$ 两点之间的简单路径上的所有节点的 $c_i=2$。

特别地，对于询问操作，若询问的节点只有一个，只需依次输出该节点 $a_i,b_i,c_i$ 的值即可，否则，依次输出对应节点 $a_i$ 的和、$b_i$ 的和、$c_i$ 的和。由于答案可能很大，对于所有询问操作，你只需要输出答案在模 $10^9+7$ 下的结果即可。

输入格式

从标准输入读入数据。

第一行输入两个整数 $n,m$，分别代表树上节点的个数和操作个数。

第二行输入 $n$ 个整数 $a_i$。

第三行输入 $n$ 个整数 $b_i$。

第四行输入 $n$ 个整数 $c_i$。

其中 $a_i,b_i,c_i$ 分别表示节点 $i$ 的初始点权。

第五行输入 $n$ 个整数 $p_i$，其中 $p_i$ 表示节点 $i$ 的父节点编号，题目保证 $1\le p_i<i$，且只有 $p_1=0$，表示节点 $1$ 为根节点。

接下来 $m$ 行，每行输入若干个整数，表示一次操作，操作格式如题面所示。

输出格式

输出到标准输出。

对于每次询问操作，输出一行由一个空格分隔的三个整数，表示你的答案。

5 7
1 1 2 2 1
2 1 3 1 2
1 1 2 1 2
0 1 1 2 2
1 2 3
2 1 2
3 3 3 4
4 2 2 1
5 7 3 3 5
6 1 1 4
7 2 1

24 39 24

子任务

对于 $40\%$ 的测试数据，保证 $1\leq n,m\leq 10^3$。

对于另外 $20\%$ 的测试数据，保证 $O\geq 4$。

对于 $100\%$ 的测试数据，保证 $1\leq n,m\leq 10^5,~1\leq a_i,b_i,c_i,v\leq 10^9$。

提示

本题输入量较大，请采用效率较高的读入方式。