{"raw_statement":[{"iden":"background","content":"题目来自原 BZOJ，我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益，可联系我们。"},{"iden":"statement","content":"浩浩荡荡的 cg 大军发现了一座矿产资源极其丰富的城市，他们打算在这座城市实施新的采矿战略。\n\n这个城市可以看成一棵有 $n$ 个节点的有根树，我们把每个节点用 $1$ 到 $n$ 的整数编号。为了方便起见，对于任何一个非根节点 $v$，它任何一个祖先的编号都严格小于 $v$。树上的每个节点表示一个矿点，每条边表示一条街道。\n\n作为 cg 大军的一个小队长，你拥有 $m$ 个部下。你有一张二维的动态信息表，用 $T_{i,j}$ 表示第 $i$ 行第 $j$ 列的数据。当你被允许开采某个区域时，你可以将你的部下分配至各个矿点。在第 $i$ 个矿点安排 $j$ 个人可以获得 $T_{i,j}$ 单位的矿产。\n\n允许开采的区域是这样描述的：给你一对矿点 $(u,v)$，保证 $v$ 是 $u$ 的祖先（这里定义祖先包括 $u$ 本身）；$u$ 为你控制的区域，可以在以 $u$ 为根的子树上任意分配部下；$u$ 到 $v$ 的简单路径（不包括 $u$ 但包括 $v$，若 $u=v$ 则包括 $u$）为探险路径，在该路径上你可以选择至多一个矿点安排部下。你这次开采的收益为安排有部下的矿点的收益之和。"},{"iden":"input","content":"输入的第一行包含 $5$ 个正整数 $n,m,A,B,Q$。其中 $n$ 为矿点的个数，$m$ 为部下的数量。$A,B,Q$ 是与动态信息表有关的数据。\n\n第二行包含 $n-1$ 个正整数，第 $i$ 个数为 $F_{i+1}$，表示节点 $i+1$ 的父亲。\n\n接下来需要你用下文的方法依次生成 $n$ 组数据，每组数据共 $m$ 个。其中第 $i$ 组的 $m$ 个数据为信息表中第 $i$ 行的 $m$ 个数据。紧接着一行包含一个正整数 $C$，表示事件的数量。\n\n最后给出 $C$ 行，每行描述一个事件。每个事件会先给出一个 $0$ 或 $1$ 的整数。如果该数为 $0$，则后面有一个正整数 $p$，表示动态信息表有更新，你需要生成一组 $m$ 个数据，来替换信息表中第 $p$ 行的 $m$ 个数据。如果该数为$1$，则后面有两个正整数 $u,v$，表示出现了一个你可以开采的区域，你需要回答这次开采的收益。同一行的各个数之间均用一个空格隔开，没有多余的空格和换行。\n\n数据的生成方法如下：每次生成一组 $m$ 个从小到大排列的数据，替换动态信息表的一行。其中，从小到大第 $j$ 个数替换信息表中第 $j$ 列的数。调用以下代码 $m$ 次并排序得到一组数据。（注意可能会出现重复的数）\n\n```\nFunction GetInt \n\nA←((A xor B)+(B div X)+(B * X))and Y \nB←((A xor B)+(A div X)+(A * X))and Y \n\nreturn (A xor B)mod Q \n```\n\n其中 $A,B,Q$ 均用 $32$ 位有符号整数保存（C/C++ 的 signed long int 类型，pascal 的 longint 类型），$X=2^{16}$，$Y=2^{31}-1$，xor 为位异或运算，div 为整除运算，and 为位且运算，mod 为取余运算。由于只保留了低 $31$ 位，易得我们不用考虑数据的溢出问题。注意每次 $A$ 和 $B$ 都会被改变）"},{"iden":"output","content":"对于每个开采事件（开头为 $1$ 的事件），输出一行一个整数，为每次的收益。"},{"iden":"note","content":"**【样例解释】**\n\n最初的信息表如下：\n\n| 0 | 1 | 1 | 2 | 2 |\n| :----------: | :----------: | :----------: | :----------: | :----------: |\n| 0 | 5 | 7 | 7 | 9 |\n| 1 | 2 | 3 | 4 | 5 |\n| 0 | 1 | 2 | 4 | 5 |\n| 2 | 4 | 7 | 8 | 8 |\n| 0 | 2 | 3 | 8 | 9 |\n| 1 | 3 | 5 | 6 | 8 |\n| 3 | 3 | 3 | 7 | 8 |\n| 0 | 1 | 2 | 3 | 9 |\n| 0 | 0 | 1 | 4 | 4 |\n\n变化后的第 $1$ 行，为：\n```\n1 1 1 4 7\n```\n第一次开采可以在矿点 $6,8,9,10$ 任意安排，可以在矿点 $3$ 或 $4$ 中选取一个安排开采。一种最优安排是在矿点 $6$ 安排 $4$人，在矿点 $8$ 安排 $1$ 人。第二次开采可以在矿点 $9$ 安排，可以在矿点 $6,4,3,1$ 中选择一个安排。一种最优安排是在矿点 $9$ 安排 $1$ 人，在矿点 $6$ 安排 $4$ 人。\n\n**【数据范围】**\n\n有 $50\\%$ 的数据，对于满足 $2\\leq i\\leq n$ 的整数 $i$，$F_i=i-1$。这些数据中有 $40\\%$ 的数据（即所有数据的 $20\\%$）满足 $n\\leq 500，m\\leq 20，C\\leq 500$。\n\n除上述数据，另有 $40\\%$ 的数据满足 $n\\leq 500$，$m\\leq 20$，$C\\leq 500$。\n\n对于 $100\\%$ 的数据 $1\\leq n\\leq 20000$，$1\\leq m\\leq 50$，$1\\leq C\\leq 2000$。对于满足 $2\\leq i\\leq n$ 的整数 $i$，$1\\leq F_i