The definition of a valid bracket sequence in this problem is 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.

The definition of a substring and distinct substrings in this problem is as follows: 1. A substring of a string $S$ is a string formed by any number of consecutive characters in $S$. A substring of $S$ can be represented by its starting position $l$ and ending position $r$, denoted as $S(l, r)$ ($1 \le l \le r \le |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.

Description

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

Little Q is a curious child. One day on his way to school, he encountered a tree of size $n$. The nodes of the tree are numbered from $1$ to $n$, with node $1$ being the root. Except for node $1$, every 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 discovered that each node in the tree has exactly one bracket, which is either '(' or ')'. Little Q defines $s_i$ as the string formed by the brackets on the simple path from the root to node $i$, arranged in the order they are visited.

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

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

$$(1 \times k_1) \oplus (2 \times k_2) \oplus (3 \times k_3) \oplus \dots \oplus (n \times k_n)$$

where $\oplus$ is the bitwise XOR operation.

Input

The first line contains an integer $n$, representing the size of the tree. The second line contains a bracket string of length $n$ consisting of '(' and ')', where the $i$-th bracket represents the bracket on node $i$. The third line contains $n-1$ integers, where the $i$-th ($1 \le i < n$) integer represents the parent $f_{i+1}$ of node $i+1$.

Output

A single integer representing the answer.

Examples

Input 1

5
(()()
1 1 2 2

Output 1

6

Note 1

The structure of the tree is as follows:

Input 2

(input data from brackets2.in)

Output 2

(output data from brackets2.ans)

Input 3

(input data from brackets3.in)

Output 3

(output data from brackets3.ans)

Constraints