题目背景

“我已经买不起第二个机器人了。”

“那就雇点人来凑数吧。注意别给死里头。”

---

题目描述

你是一个矿坑老板。

你的矿坑是二叉树形结构，有 $n$ 个节点。$1$ 号点为地面，对于所有的 $2 \le i \le n$，$i$ 号节点与更浅层的 $f_i$ 号节点通过通道相连，其中 $f_i < i$，且相同的 $f_i$ 最多出现两次。

矿坑的不同节点的产量和开采难度均不相同。对于 $i$ 号节点 $(2 \le i \le n)$：

• 如果派一个机器人开采，一单位时间内能有 $r_i$ 的产出
• 如果派一个人类开采，一单位时间内能有 $p_i$ 的产出

地面（$1$ 号节点）没有产出。

你有一个机器人，初始位于 $s$ 号节点。你的矿坑里初始没有人类工人。

移动规则：

• 每个节点只能容下一名工人（人类或机器人）
• 每个通道只能恰好容一名工人通过
• 在移动的任何时刻，只能有最多一名工人在通道中，其余工人都必须在节点上

---

计划执行

有 $q$ 条计划需要按顺序执行。每个计划分为四个阶段：

1. 准备阶段：人类可以在满足移动规则的前提下任意移动，但不能进入或离开矿坑（到达 $1$ 号节点不算离开）。机器人不能移动。
2. 执行阶段（共 $4$ 种）：
   • 类型 1：机器人只能沿通道向更浅的方向移动，且至少经过一条通道。人类不能移动。
   • 类型 2：机器人只能沿通道向更深的方向移动，且至少经过一条通道。人类不能移动。
   • 类型 3：使一名人类从 $1$ 号节点进入矿坑（开始时 $1$ 号节点必须没有工人）。其他工人不能移动。
   • 类型 4：使一名人类从 $1$ 号节点移出矿坑（开始时 $1$ 号节点必须有一名人类）。其他工人不能移动。
3. 调整阶段：限制与准备阶段相同。
4. 开采阶段：所有工人采一单位时间的矿。有工人的非地面节点按其工人种类计算产出。该计划的产出为所有节点的产出之和。

问按顺序执行完所有计划后，所有计划的产出之和的最大值。

---

输入格式

第一行三个正整数 $n, q, s$。

第二行 $n-1$ 个整数，其中第 $i$（$1 \le i < n$）个表示 $f_{i+1}$。

第三行 $n-1$ 个整数，其中第 $i$ 个表示 $r_{i+1}$。

第四行 $n-1$ 个整数，其中第 $i$ 个表示 $p_{i+1}$。

接下来 $q$ 行，每行一个整数表示计划的种类：

• $1$：机器人向更浅方向移动
• $2$：机器人向更深方向移动
• $3$：送入一名人类
• $4$：移出一名人类

---

输出格式

如果无法完成计划，输出 No solution.。

否则输出一个整数，表示产出之和的最大值。

---

样例

输入：

5 6 4
1 1 3 3
15 9 7 1
4 2 8 6
3
3
1
2
2
4

输出：

91

解释：一个最优解如下（部分阶段略过）：

• 第一个计划调整阶段：将刚送入的人类移动到 $5$ 号点
• 开采：机器人产出 $7$，人类产出 $6$
• 第二个计划调整阶段：将新人类移动到 $2$ 号点
• 开采：机器人产出 $7$，人类产出 $4+6=10$
• 第三个计划执行阶段：机器人移动到 $1$ 号点
• 调整阶段：一名人类从 $5$ 移动到 $4$
• 开采：机器人产出 $0$，人类产出 $4+8=12$
• 第四个计划准备阶段：一名人类从 $4$ 移动到 $5$
• 执行阶段：机器人移动到 $3$ 号点
• 开采：机器人产出 $9$，人类产出 $4+6=10$
• 第五个计划执行阶段：机器人移动到 $4$ 号点
• 开采：机器人产出 $7$，人类产出 $4+6=10$
• 第六个计划准备阶段：一名人类从 $2$ 移动到 $1$
• 开采：机器人产出 $7$，人类产出 $6$

总产出：$7+6 + 7+10 + 0+12 + 9+10 + 7+10 + 7+6 = 91$

---

数据范围

• $2 \le n \le 301$
• $1 \le q \le 600$
• $1 \le s \le n$
• $1 \le f_i < i$
• $0 \le r_i, p_i \le 10^9$
• 相同的 $f_i$ 最多出现两次（二叉树）

---