题目背景

题目提供者：XuKaFy

题目描述

【原版题目】

给定一颗 $n$ 个节点的树，树的叶节点全部是数字，非叶节点全部是符号 + 或者 *。

请先对该树进行树链剖分。注意：若出现子树大小相同的情况，请选择编号较小的子节点作为重儿子。

一个节点的权值这样计算：若该节点为叶节点，数值即为节点数值；若该节点非叶节点，则该点的权值为【【【该点的【所有不在该点所在重链上】的子节点】所在重链的所有节点权值】相 + 或者相 * 的结果（操作取决于该节点的符号）】。

另一种表示方式是：设某一节点 $i$ 的儿子集合为 $D_{i}$，节点 $i$ 的父亲为 $F_{i}$，节点 $i$ 的所在重链节点集合为 $P_{i}$。

我们设：

$$Charge_{i}=\cup_{k\in D_{i},\ k\not\in P_{i}}P_{k} $$

令 $C_{i}$ 为这个节点的符号，这个节点的权值就是：

$$V_{i}= \begin{cases} \sum_{j\in Charge_{i}}V_{j} &C_{i}=`+'\\ \prod_{j\in Charge_{i}}V_{j} &C_{i}=`\times' \end{cases} $$

数据不保证每一个非叶节点都有至少一个非链上儿子，若没有合法的儿子则忽略该节点。

你需要支持这三种操作：

1. 改变某一叶节点的数值；

2. 改变某一非叶节点的符号为 + 或者 *；

3. 查询某一节点所在重链所有节点权值相 + 与相 * 的值。

为防止溢出，请将所有权值对 $99991$ 取模。

输入格式

第一行输入两个数 $n$ 与 $m$ 表示学生数量与要求数量。

接下来输入 $1$ 行，$n-1$ 个数，表示第 $i+1$ 个节点的父亲为$a$。

接下来一行 $n$ 个数，分别为每个节点的信息：若该节点为叶节点，则是一个数字表示 $V_{i}$，否则为一个数，0 表示 +，1表示 *。

接下来输入 $m$ 行，每行一个数字 $c$ 与编号 $k$，表示要求类型为 $c$，操作的节点编号为 $k$。若 $c=1$，那么再输入一个数 $V_{i}$ 表示新的权值。

输出格式

对于每一个 $3$ 操作，请输出一行，该行包括两个数 $a, b$，分别表示将本节点所在重链的所有节点权值相加以及相乘的结果。

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

18 132
37 360
35 120

提示

对于 $30\%$ 的数据，$1 \le n,m \le 1000$。

对于 $100\%$ 的数据，$1 \le n,m \le 10^{6}, 1 \le V_{i}<99991$。

数据保证任何时刻树上没有权值为 $0$ 的节点。