Description

ISTP is not MBTI, but the task you need to perform: Insert and Search 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.

Your task is to perform T insertion or search operations:

• insert A: 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.
• search B: Find the node with the B-th largest value in the tree and return its value. B is guaranteed to be between 1 and the total number of nodes in the tree.

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.

• insert: Insert a node with value A into the parentheses tree.
• search: Find the node with the B-th largest value in the tree and print its value.

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 / search operations to perform.
The following T lines each contain either an insert A operation or a search B operation.

Constraints

• 0 ≤ N ≤ 10⁶
• 1 ≤ T ≤ 1000
• -10⁹ ≤ D, A ≤ 10^9​
• 1 ≤ B ≤ all nodes in the tree

Subtask

• Testcases 1 ~ 3: insertion operation
• Testcases 4 ~ 6: No additional restrictions

Output

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

Sample Input  Download

Sample Output  Download

Partial Judge Code

14586.c

Partial Judge Header

14586.h

Tags

Discuss