CSES - Xor subtrees
  • Time limit: 4.00 s
  • Memory limit: 1024 MB

We have a rooted tree indexed in post-order (parent after all nodes in subtree), and want to find the group AnA_{n} (the group can contain the same element multiple times). AjA_{j} is defined as follows:

For a leaf with index jj, Aj=[j]A_{j} = [j]

For a node jj with kk children c1,c2,,ckc_{1}, c_{2}, \cdots, c_{k}, let vj=min(i=1kAci)v_{j} = min(\cup_{i = 1}^{k} A_{c_{i}}). Now:

Aj=Ac1++Ack[vj]+[vjj]+[j]A_{j} = A_{c_{1}} + \cdots + A_{c_{k}} - [v_{j}] + [v_{j} \oplus j] + [j].

Where ++ makes a group that contains the elements of both groups, and - makes a group with a copy of every element from the second group removed from the first group. Note that a group can contain multiples of the same element. [3,3][3]=[3][3, 3] - [3] = [3].

Can you calculate the sum of all elements in AnA_{n} (that is, the root node)?

Input

Since the input is very large, it is given in a special form.

The tree is represented as a bracket sequence of length 2n2n. A node starts with a opening bracket, then children follow, and then the node is closed by a closing bracket. For example, a node with no children is (), and a node with two children, the second of which has one child, is (()(())). The child that appears first is first in the postorder traversal too.

The first line of input contains the integer nn.

Then you are given 2n64\left\lceil \frac{2n}{64} \right\rceil unsigned 6464-bit integers. The ii'th bit (representing 2i2^{i}) of the jj'th integer is 11 if the (64j+i)(64j + i)'th character in the bracket sequence is "(", and 00 if it's ")". After the end of the bracket sequence all bits are 00.

Output

Output the sum of all elements in AnA_{n}.

Constraints

  • 1n1071 \leq n \leq 10^{7}

Example

Input:

4
39

Output:

16

Explanation:

The bracket sequence is ((())()). A1=[1]A_{1} = [1], A2=[2,3]A_{2} = [2, 3], A3=[3]A_{3} = [3], A4=[3,3,4,6]A_{4} = [3, 3, 4, 6]