Distinct Valid Bracket Substrings on a Tree

You are given a tree with n nodes numbered from 1 to n. The tree has exactly n - 1 edges, and each edge connects two nodes such that there exists exactly one simple path between any two nodes. Node 1 is the root of the tree. For every node u (where 2 ≤ u ≤ n), its parent is given by f₍ᵤ₎ (with 1 ≤ f₍ᵤ₎ < u).

Each node has exactly one bracket on it – either ( or ). For every node i (1 ≤ i ≤ n), define s_i as the bracket string obtained by concatenating, in order, the brackets on the simple path from the root to node i. Note that s_i is a bracket sequence, but it might not be a valid bracket sequence.

A valid bracket sequence is defined in the usual way – for example, () and ()() are valid, while ( and ) ( are not.

Let k_i be the number of distinct substrings of s_i that are valid bracket sequences. You are to compute the value:

[ (1 \times k_1) ;\text{xor}; (2 \times k_2) ;\text{xor}; \cdots ;\text{xor}; (n \times k_n) ]

Here, \(xor\) denotes the bitwise XOR operation.

Input Format: The input begins with an integer n. The next line contains n-1 integers, where the u-th integer (for 2 ≤ u ≤ n) is f₍ᵤ₎, the parent of node u. The last line contains a string of length n consisting of the characters ( and ), where the i-th character is the bracket on node i.

Output Format: Output a single integer representing the XOR of i × k_i for all nodes i from 1 to n.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵, though the test cases provided will be small).

The second line contains n - 1 integers: f₂, f₃, ..., fₙ where 1 ≤ fᵤ < u for each 2 ≤ u ≤ n, representing the parent of node u.

The third line contains a string of length n consisting only of the characters ( and ), where the i-th character is the bracket on node i.

outputFormat

Output a single integer which is the XOR of all i × k_i for 1 ≤ i ≤ n.

sample

3
1 1
(()

3