题目背景

  「几枝新叶萧萧竹，数笔横皴淡淡山」

---

  十几天前的那条路，还好，两个人一起。

  “很幸运呢”，阿绫悄悄嘬一口才破涕为笑的天依，“上天保佑我们要在一……”

  鼓着腮掐着软软的腰，天依却又不觉流露笑意，是很幸运呢，刚好入围……

  鳞次栉比的尽头，天空似云下起伏的山，皴擦着淡青墨样的欣喜。

  她们的故事还在继续，正如谷物正当在今日生长。

---

  谷雨 「我翻过一座高山　前方依然　山路漫漫」

题目描述

老 V 为发挥不错的大家办了场小 party，为了活跃气氛，同时贯彻安全环保的理念，（主要还是因为编不出来了，） 老 V 带来了一个高大上的“电子烟花”，美其名曰，火树银花。

物如其名，这是一棵含有 $n$ 个结点的树，结点 $u$ 上有点权 $l_u$，表示该结点上所设烟花样式的绚丽度。好奇的大家一共对它进行了 $q$ 次操作，不妨记树上从 $u$ 到 $v$ 的路径上的结点（含 $u,v$）构成集合 $P(u,v)$，则每次操作形如：

0. 给定结点编号 $u,v$ 和新的绚丽度 $k$，意为将所有 $\in P(u,v)$，或者存在一个邻接点 $\in P(u,v)$ 的结点 $w$ 的绚丽度 $l_w$ 赋值为 $k$。

1. 给定 $u,v$，点燃这一串烟花最“耀眼”的子段。具体地，维护一个序列 $S$，从 $u$ 出发沿着树边走向 $v$，当走到结点 $w$（$w$ 可能为 $u$ 或 $v$） 时：

   • 将 $l_w$ 加入序列 $S$ 的末尾；
   • 按标号从小到大枚举 $w$ 的邻接点 $x$，若 $x\notin P(u,v)$，将 $l_x$ 加入 $S$ 的末尾；
   • 最后，走向下一个结点。

得到最终的 $S$ 后，系统将自动点燃 $S$ 中绚丽度之和最大的子段，子段可能为空。而你需要求出这一和的最大值，即对于每次 1. 操作，求出 $S$ 的最大可空子段和。

输入格式

第一行一个整数 $T$，表示该测试数据所属的子任务编号。

第二行一个整数 $n$，表示树的结点个数。

第三行 $n$ 个整数，第 $i$ 个整数 $l_i$ 表示结点 $i$ 的初始权值。

第四行 $n-1$ 个整数，为方便选手处理数据，此处假设 $1$ 号结点为树的根。 第 $i$ 个整数 $p_i$ 表示结点 $i+1$ 的父亲，即表述一条边 $(p_i,i+1)$。保证 $p_i<i+1$。

第五行一个整数 $q$，表示需要处理的操作数量。

接下来 $q$ 行，每行格式为 $0~u~v~k$ 或者 $1~u~v$，分别对应了「题目描述」中的两种操作。

输出格式

输出有若干行，第 $i$ 行应包含一个整数 $a_i$，表示第 $i$ 次 1. 操作的答案。

0
5
1 2 3 4 5
1 2 2 1
5
1 1 2
0 2 3 -2
1 3 4
0 4 4 1
1 3 4

15
0
1

提示

样例 #1 解释

本组样例不属于测试数据，故第一行 $T$ 以 $0$ 代替。

第 $1$ 次操作为询问，依次遍历到的结点为 $\lang 1,5,2,3,4\rang$，对应权值队列 $S=\lang 1,5,2,3,4\rang$，最大子段和为 $15$。

第 $2$ 次操作为修改，将结点 $2,1,4,3$ 的点权修改为 $-2$。

第 $3$ 次操作为询问，依次遍历到的结点为 $\lang 3,2,1,4\rang$，对应权值队列 $S=\lang -2,-2,-2,-2\rang$，注意子段可以为空，所以最大子段和为 $0$。

第 $4$ 次操作为修改，将结点 $4,2$ 的点权修改为 $1$。

第 $5$ 次操作为询问，依次遍历到的结点为 $\lang 3,2,1,4\rang$，对应权值队列 $S=\lang -2,1,-2,1\rang$，最大子段和为 $1$。

数据规模与约定

本题采用 Subtask 的计分方式。

设 $V$ 为初始点权以及修改操作中点权的值域。

对于 $100\%$ 的数据，$1\le n,q\le10^5$，$1\le p_i\le i$，$V\subseteq[-10^9,10^9]$，操作参数 $1\le u,v\le n$。

对于不同的子任务，作如下约定：

子任务编号	$n,q$	$V$	特殊性质	子任务分值
$1$	$\le10^3$	$\subseteq[-10^9,10^9]$	无	$10$
$2$	$\le10^5$		A
$3$			B
$4$			C	$15$
$5$			D
$6$		$\subseteq[0,10^9]$	无	$10$
$7$		$\subseteq[-10^9,10^9]$	E	$20$
$8$			无	$10$

• 特殊性质 A：对于所有 $i\in[1,n)$，满足 $p_i=i$。
• 特殊性质 B：对于所有操作中的参数 $u,v$，满足 $u=v$。
• 特殊性质 C：不存在修改操作。
• 特殊性质 D：有且仅有第 $q$ 次操作是询问操作。
• 特殊性质 E：对于所有询问操作中的参数 $u,v$，满足当结点 $1$ 为树根时，$u=v$ 或 $u$ 是 $v$ 的祖先。
• 注意：输入数据中的 $T$ 仅指该数据点所属子任务编号，该数据点可能满足其他子任务的约束条件。