Person in Charge

Problem Background

The definition of a valid parentheses string in this problem is as follows:

1. () is a valid parentheses string.
2. If A is a valid parentheses string, then (A) is a valid parentheses string.
3. If A and B are valid parentheses strings, then AB is a valid parentheses string.

The definitions of substring and distinct substrings in this problem are as follows:

1. A substring of string S is a string composed of consecutive arbitrary number of characters in S. A substring of S can be represented by the starting position $l$ and ending position $r$, denoted as $S (l, r)$ ($1 \le l \le r \le |S|$, where $|S|$ represents the length of $S$).
2. Two substrings of S are considered distinct 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 there is exactly one simple path between any two nodes that is reachable from each other.

Little Q is a curious child. One day on his way to school, he encountered a tree of size $n$, where the nodes are numbered from $1$ to $n$, and node $1$ is the root of the tree. Except for node $1$, each node has a parent node: the parent of node $u$ ($2 \le u \le n$) is node $f_u$ ($1 \le f_u < u$).

Little Q found that each node of the tree has exactly one parenthesis, which can be ( or ). Little Q defines $s_i$ as the string formed by arranging the parentheses on the simple path from the root node to node $i$ in the order of the nodes passed.

Obviously, $s_i$ is a parentheses string, but not necessarily a valid one. Therefore, Little Q now wants to find, for each $i$ ($1\le i\le n$), the number of distinct substrings of $s_i$ that are valid parentheses strings.

This problem stumped Little Q, so he had to ask for your help. Let $k_i$ be the number of distinct substrings of $s_i$ that are valid parentheses strings. You only need to tell Little Q the XOR sum of all $i \times k_i$, i.e.:

$$(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}$ denotes the bitwise XOR operation.

Input Format

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

The second line contains a parentheses string of length $n$ composed of ( and ), where the $i$-th parenthesis represents the parenthesis on node $i$.

The third line contains $n - 1$ integers, where the $i$-th integer ($1 \le i \lt n$) represents the parent number $f_{i+1}$ of node $i + 1$.

Output Format

Output a single integer representing the answer.

Samples

5
(()()
1 1 2 2

6

Sample 1 Explanation

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

• The string formed by arranging the parentheses on the simple path from the root to node $1$ is (, and the number of substrings that are valid parentheses strings is $0$.
• The string for the path from the root to node $2$ is ((, and the number of valid parentheses substrings is $0$.
• The string for the path from the root to node $3$ is (), and the number of valid parentheses substrings is $1$.
• The string for the path from the root to node $4$ is (((, and the number of valid parentheses substrings is $0$.
• The string for the path from the root to node $5$ is ((), and the number of valid parentheses substrings is $1$.

Sample 2

See brackets/brackets2.in and brackets/brackets2.ans in the contestant's directory.

Sample 3

See brackets/brackets3.in and brackets/brackets3.ans in the contestant's directory.

Data Range

Test Case 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$

For $100\%$ of the data: $1 \le n \le 5 \times 10^5$, $1 \le f_i \le i-1$.