- 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 (the group can contain the same element multiple times). is defined as follows:
For a leaf with index ,
For a node with children , let . Now:
.
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. .
Can you calculate the sum of all elements in (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 . 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 .
Then you are given unsigned -bit integers. The 'th bit (representing ) of the 'th integer is if the 'th character in the bracket sequence is "("
, and if it's ")"
. After the end of the bracket sequence all bits are .
Output
Output the sum of all elements in .
Constraints
Example
Input:
4 39
Output:
16
Explanation:
((())())
. , , ,