Problem L
Animal Classification

Alice and Bob are biologists. They like to group animals using classification trees. A classification tree is a binary tree where the leaves are labeled by the animals.

For example, Figure 1 below shows the classification of $5$ animals (labeled as $1, 2, 3, 4, 5$) by Alice and Bob. Alice’s classification has nine groups: $\{ 1\} $, $\{ 2\} $, $\{ 3\} $, $\{ 4\} $, $\{ 5\} $, $\{ 2, 5\} $, $\{ 1, 2, 5\} $, $\{ 1, 2, 3, 5\} $ and $\{ 1, 2, 3, 4, 5\} $. Bob’s classification also has nine groups: $\{ 1\} $, $\{ 2\} $, $\{ 3\} $, $\{ 4\} $, $\{ 5\} $, $\{ 1, 5\} $, $\{ 2, 3\} $, $\{ 1, 2, 3, 5\} $ and $\{ 1, 2, 3, 4, 5\} $.

Figure 1: Illustration of Sample Input 1

As you can observe, Alice and Bob classify the animals differently. Carol is interested to know the number of common groups between the classifications of Alice and Bob. For the above example, there are $7$ common groups. They are: $\{ 1\} $, $\{ 2\} $, $\{ 3\} $, $\{ 4\} $, $\{ 5\} $, $\{ 1, 2, 3, 5\} $ and $\{ 1, 2, 3, 4, 5\} $.

Carol usually counts the number of common goups by hand. On one day, an outer space alien came to our earth. He asked Alice and Bob to classify aliens in outer space. The number $N$ of aliens can be as big as $100\, 000$. It is impossible to count the number of common goups by hand now. Can you make a program to help Carol?

Input

The input consists of three lines:

• one line with one integer $N$ ($1 \leq N \leq 100\, 000$)

• the classification tree of Alice

• the classification tree of Bob

Note that both classification trees are leaf-labeled by $1$ to $N$. The tree is represented by the parathesis encoding. (Note that the encoding only have numbers and $3$ symbols, that is, ‘(’, ‘)’, ‘,’.) For the example in Figure 1, see Sample Input 1.

Output

Output one line with a single integer that represents the number of common groups between Alice and Bob’s classification trees.

5
((3,(1,(5,2))),4)
(((5,1),(2,3)),4)

7

10
(1,(2,(3,(4,(5,(6,(7,(8,(9,10)))))))))
(((((((((1,2),3),4),5),6),7),8),9),10)

11

10
(10,(9,(8,(7,(6,(5,(4,(3,(2,1)))))))))
(((((((((1,2),3),4),5),6),7),8),9),10)

19