Expression Tree

An expression tree is a rooted binary tree with 2N-1 nodes. Nodes 1 through N are operand nodes, the remaining nodes are operator nodes, and node 2N-1 is the root.

An operator node always has two children and holds the operator '+' or '-'.

An operand node has no children and holds a single integer.

The expression tree is evaluated as follows.

1. Choose an operator node whose two children are operand nodes.
2. If the operator of that node is '+', replace the operator node with an operand node whose value is the sum of the left node's value and the right node's value. If the operator is '-', replace the operator node with an operand node whose value is the left node's value minus the right node's value.

After performing this N-1 times, one number remains, and that is the result of the expression.

Before starting the evaluation, Jinsu may choose two operand nodes in the initial expression tree and swap the integers they hold. Given an expression tree, Jinsu's task today is to swap the integers in the nodes as many times as he likes so that the result of the expression tree is maximized.

The expression is too large to evaluate by hand. Help Jinsu.

The first line gives the integer N (2 ≤ N ≤ 100,000).

The next N lines give the integer aᵢ (-10,000 ≤ aᵢ ≤ 10,000) held by operand nodes 1 through N.

The next N-1 lines give information about operator nodes N+1 through 2N-1.

Each line gives the operator oᵢ held by the operator node (oᵢ ∈ {'+', '-'}), the number of its left child, and the number of its right child cᵢ,₁, cᵢ,₂ (1 ≤ cᵢ,₁, cᵢ,₂ ≤ 2N-2) in that order.

The input is guaranteed to be a valid tree that can be evaluated.

Print on the first line the maximum result obtainable by swapping the integers held by the operand nodes.