Background

In this problem, a valid bracket sequence is defined as follows:

1. () is a valid bracket sequence.
2. If A is a valid bracket sequence, then (A) is a valid bracket sequence.
3. If A and B are valid bracket sequences, then AB is a valid bracket sequence.

In this problem, the definitions of a substring and distinct substrings are as follows:

1. A substring of a string S is a string formed by any continuous characters in S. A substring of S can be represented by the starting position $l$ and the ending position $r$, denoted as $S (l, r)$ ($1 \leq l \leq r \leq |S |$, where $|S |$ denotes the length of S).
2. Two substrings of S are considered different if and only if their positions in S are different, i.e. $l$ is different or $r$ is different.

Problem Description

A tree of size $n$ contains $n$ nodes and $n - 1$ edges. Each edge connects two nodes, and between any two nodes there exists exactly one simple path.

Xiao Q is a curious kid. One day on his way to school, he encountered a tree of size $n$. The nodes of the tree are numbered from $1 \sim n$, and node $1$ is the root. Except for node $1$, every node has a parent node. The parent of node $u$ ($2 \leq u \leq n$) is node $f_u$ ($1 \le f_u < u$).

Xiao Q found that each node of the tree has exactly one bracket, either ( or ). Xiao Q defines $s_i$ as follows: take the brackets on the simple path from the root to node $i$, and arrange them into a string in the order the nodes are visited.

Obviously, $s_i$ is a bracket string, but it is not necessarily a valid bracket sequence. Now Xiao Q wants, for all $i$ ($1 \leq i \leq n$), to find how many distinct substrings of $s_i$ are valid bracket sequences.

This problem stumped Xiao Q, so he asks you for help. Suppose $s_i$ has $k_i$ distinct substrings that are valid bracket sequences. You only need to tell Xiao Q the XOR sum of all $i \times k_i$, namely:

$$(1 \times k_1)\ \text{xor}\ (2 \times k_2)\ \text{xor}\ (3 \times k_3)\ \text{xor}\ \cdots\ \text{xor}\ (n \times k_n)$$

where $\text{xor}$ is the bitwise XOR operation.

Input Format

The first line contains an integer $n$, denoting the size of the tree.

The second line contains a bracket string of length $n$ consisting of ( and ). The $i$-th bracket denotes the bracket on node $i$.

The third line contains $n − 1$ integers. The $i$-th integer ($1 \leq i \lt n$) denotes the parent index $f_{i+1}$ of node $i + 1$.

Output Format

Only one line containing one integer, denoting the answer.

5
(()()
1 1 2 2

6

Hint

[Sample 1 Explanation]

The shape of the tree is shown in the figure below:

The string formed by the brackets on the simple path from the root to node 1, arranged in order, is (, and the number of substrings that are valid bracket sequences is $0$.

The string from the root to node 2 is ((, and the number of substrings that are valid bracket sequences is $0$.

The string from the root to node 3 is (), and the number of substrings that are valid bracket sequences is $1$.

The string from the root to node 4 is (((, and the number of substrings that are valid bracket sequences is $0$.

The string from the root to node 5 is ((), and the number of substrings that are valid bracket sequences is $1$.

[Sample 2]

See brackets/brackets2.in and brackets/brackets2.ans under the contestant directory.

[Constraints]

::cute-table{tuack}

Test Point ID	$n\le$	Special Property
$1\sim 2$	$8$	$f_i=i-1$
$3\sim 4$	$200$	^
$5\sim 7$	$2000$
$8\sim 10$	^	None
$11\sim 14$	$10^5$	$f_i=i-1$
$15\sim 16$	^	None
$17\sim 20$	$5\times 10^5$	^

Translated by ChatGPT 5