_“I can no longer afford a second robot.”_

_“Then hire some humans to make up the numbers. Just be careful not to get them killed.”_

You are a mine owner.

Your mine is structured as a binary tree with $n$ nodes. Node $1$ is the ground level. For all $2 \le i \le n$, node $i$ is connected to its parent node $f_i$ via a tunnel, where $f_i < i$, and each $f_i$ appears at most twice. Different nodes in the mine have different production rates and mining difficulties. For node $i$ ($2 \le i \le n$), if a robot is assigned to mine, it produces $r_i$ units per unit of time; if a human is assigned to mine, they produce $p_i$ units per unit of time. The ground level produces nothing.

You have one robot, initially located at node $s$. There are no human workers in your mine initially.

All tunnels and nodes are very narrow; each node can hold at most one worker (humans and robots alike), and each tunnel can hold exactly one worker at a time. At any moment during movement, at most one worker can be in a tunnel, and all other workers must be at nodes.

You have $q$ plans that must be executed in order. Each plan consists of four phases: Preparation, Execution, Adjustment, and Mining.

In the Preparation phase, humans can move arbitrarily as long as they satisfy the movement rules above, but they cannot enter or leave the mine (workers reaching node $1$ are not considered to have left the mine), as you are watching them. There are no restrictions on the order or number of moves. The robot cannot move.

In the Execution phase, the tasks vary depending on the plan, categorized into 4 types:

1. The robot must move along a tunnel towards a shallower direction (towards the root) and must traverse at least one tunnel. Humans cannot move.
2. The robot must move along a tunnel towards a deeper direction (away from the root) and must traverse at least one tunnel. Humans cannot move.
3. A human enters the mine from node $1$ (this means node $1$ must be empty at the start of this phase). No other workers can move.
4. A human leaves the mine from node $1$ (this means there must be a human at node $1$ at the start of this phase). No other workers can move.

In the Adjustment phase, the restrictions are the same as in the Preparation phase. Humans can move arbitrarily as long as they satisfy the movement rules, but they cannot enter or leave the mine. There are no restrictions on the order or number of moves. The robot cannot move.

In the Mining phase, all workers mine for one unit of time. All non-ground nodes occupied by a worker calculate production based on the type of worker at that node. Nodes without workers produce nothing. The production of the plan is the sum of the production of all nodes.

Calculate the maximum total production across all plans after executing them in order.

Input

The input is read from standard input.

The first line contains three positive integers $n, q, s$.

The second line contains $n-1$ integers, where the $i$-th integer ($1 \le i < n$) represents $f_{i+1}$.

The third line contains $n-1$ integers, where the $i$-th integer represents $r_{i+1}$.

The fourth line contains $n-1$ integers, where the $i$-th integer represents $p_{i+1}$.

The next $q$ lines each contain an integer representing the type of plan, where the $i$-th integer represents the $i$-th plan:

• 1 represents the first type of plan: move the robot towards a shallower direction.
• 2 represents the second type of plan: move the robot towards a deeper direction.
• 3 represents the third type of plan: send a human into the mine from node $1$.
• 4 represents the fourth type of plan: remove a human from the mine via node $1$.

Output

Output to standard output.

If you cannot complete your plans under any circumstances, output No solution.. Otherwise, output a single integer representing the maximum total production.

Examples

Input 1

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

Output 1

91

Note

An optimal solution is as follows (some phases with no movement are omitted):

Adjustment phase of the first plan: Move the human just sent to node $1$ twice to reach node $5$.

Mining phase of the first plan: Robot production is $7$, human production is $6$.

Adjustment phase of the second plan: Move the human just sent to node $1$ to node $2$.

Mining phase of the second plan: Robot production is $7$, human production is $4+6=10$.

Execution phase of the third plan: Move the robot to node $1$.

Adjustment phase of the third plan: Move a human from node $5$ to node $4$.

Mining phase of the third plan: Robot production is $0$, human production is $4+8=12$.

Preparation phase of the fourth plan: Move a human from node $4$ to node $5$.

Execution phase of the fourth plan: Move the robot to node $3$.

Mining phase of the fourth plan: Robot production is $9$, human production is $4+6=10$.

Execution phase of the fifth plan: Move the robot to node $4$.

Mining phase of the fifth plan: Robot production is $7$, human production is $4+6=10$.

Preparation phase of the sixth plan: Move a human from node $2$ to node $1$.

Mining phase of the sixth plan: Robot production is $7$, human production is $6$.

Total production is $7+6+7+10+0+12+9+10+7+10+7+6=91$.

Subtasks

It is guaranteed that $2 \le n \le 301$, $1 \le q \le 600$, $1 \le s \le n$.

It is guaranteed that $1 \le f_i < i$, $0 \le r_i, p_i \le 10^9$.

It is guaranteed that each $f_i$ appears at most twice.