New Year Party

A company's organization chart is a rooted tree whose root is the president. Every employee except the president has exactly one direct manager and appears directly below that manager in the tree.

The vice president is preparing a New Year party. To keep the party comfortable, an employee and that employee's direct manager cannot both be invited.

Each employee has a festivity score recorded from prior observations. The party's total festivity is the sum of the festivity scores of all invited employees.

Find guest lists that maximize the total festivity while satisfying the rule above. You must compute the answer separately for the case where the president attends and the case where the president does not attend. Scores may be negative, so when the president does not attend, inviting nobody may be optimal.

The first line contains the number of employees N, including the president. 2 <= N <= 200,000. The president is employee 1, and the other employees are numbered from 2 through N.

The second line contains N integers, the festivity scores of employees 1 through N in order. The absolute value of each integer is at most 10,000.

The third line contains N-1 integers: for each employee from 2 through N, the number of that employee's direct manager. The input always forms a valid rooted tree with employee 1 as the root.

On the first line, print two integers separated by a space: the maximum festivity when the president attends, then the maximum festivity when the president does not attend.

On the second line, print the invited employee numbers for the case where the president attends, in increasing order, followed by -1.

On the third line, print the invited employee numbers for the case where the president does not attend, in increasing order, followed by -1.