Description

INTP is not MBTI, but the task you need to perform: INsert The Parentheses tree.

You are given a binary search tree of length N represented in parentheses. The binary search tree is represented according to the following rule:

If a node is NULL, represent it as ()

Next, you will perform T insertion operations. Each operation involves inserting a node with value A. The insertion rule is as follows:

Starting from the root node, if A is less than the current node's value, move to the left subtree. If A is greater than the current node's value, move to the right subtree, until an NULL node is found. Insert a node with the value A at that NULL node.

Finally, output the binary tree after completing the operations, expressed in parentheses.

 

For sample input:
3(2(1()())())(4()())

The Parentheses tree is guaranteed to satisfy the following condition before and after all T operations:

• As a binary search tree, it ensures each node's left child is less than the node and its right child is greater.
• All node values in the tree are unique.

 

This question is a partial judge.
Please implement functions defined in the header file.

• parenthesesTree: Construct a parentheses tree based on a given parentheses expression.
• insert: Insert a node with value A into the parentheses tree.
• print: After all insertion operations are complete, output the parentheses tree as a parentheses expression.

Input

The first line contains an integer N, representing the length of the string expression of the parentheses tree.
The second line contains a parentheses expression of length N.
The third line contains an integer T, representing the number of insertion operations to perform.
The following T lines each contain an integer A, representing the value of the node to be inserted into the binary tree.

Constraints

• 0 ≤ N ≤ 10⁶
• 1 ≤ T ≤ 100
• -10⁹ ≤ D, A ≤ 10^9​

Subtask

• Testcases 1 ~ 3: T = 0
• Testcases 4 ~ 6: No additional restrictions

Output

Output the binary tree after completing the operations, expressed in parentheses.

 

Please remember to print "\n" at the end.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14582.c

Partial Judge Header

14582.h

Tags

Discuss