Conversion between (\text{Prüfer}) Sequence and Unrooted Tree

Given an unrooted tree with \(n\) vertices, we represent it in two ways:

• A parent sequence \(f_{1\dots n-1}\), where for each vertex \(i\) (\(1 \le i \le n-1\)) its parent is \(f_i\) when vertex \(n\) is regarded as the root.
• A Prüfer sequence \(p_{1\dots n-2}\) corresponding to the tree.

Your task is to perform a conversion between these two representations. You are given an operation type:

• If the operation type is 1, you are given the parent sequence (of length \(n-1\)) and you must convert it into the corresponding Prüfer sequence (of length \(n-2\)).
• If the operation type is 2, you are given the Prüfer sequence (of length \(n-2\)) and you must reconstruct the tree and output its parent sequence (of length \(n-1\)) when the tree is rooted at vertex \(n\).

After obtaining the resulting sequence \(a_{1\dots m}\) (where \(m=n-2\) for operation 1 and \(m=n-1\) for operation 2), compute its weight defined by:

[ \text{weight} = \bigoplus_{i=1}^{m} i \times a_i, ]

where \(\oplus\) denotes the bitwise XOR operation. Output the computed weight.

Note: Although the tree is unrooted, for input purposes, vertex \(n\) is always treated as the root.

inputFormat

The input begins with an integer op indicating the operation type.

• If op = 1:
• The next line contains an integer \(n\) (number of vertices).
• The following line contains \(n-1\) space-separated integers \(f_1, f_2, \dots, f_{n-1}\), representing the parent sequence (with the tree rooted at vertex \(n\)).
• If op = 2:
• The next line contains an integer \(n\) (number of vertices).
• The following line contains \(n-2\) space-separated integers \(p_1, p_2, \dots, p_{n-2}\), representing the Prüfer sequence.

outputFormat

Output a single integer representing the weight of the resulting sequence after conversion. The weight is computed as:

[ \text{weight} = \bigoplus_{i=1}^{m} i \times a_i, ]

where \(m\) is the length of the resulting sequence and \(a_i\) is its \(i\)-th element.

sample

1
4
4 4 4

12