Description

In this assignment, you will implement a Binary Search Tree (BST) that supports four fundamental operations: insertion, searching, and finding the predecessor and successor of a given key.

A Binary Search Tree is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

You will process a sequence of commands, each representing one of the following operations:

1. ins k: Insert an integer key k into the BST. If k already exists in the tree, this operation should have no effect.

2. find k: Search for the key k in the BST. Output true if it exists, and false otherwise.

3. succ k: Find the successor of k. The successor is defined as the smallest key in the tree that is strictly greater than k. If no such key exists, return null.

4. pred k: Find the predecessor of k. The predecessor is defined as the largest key in the tree that is strictly smaller than k. If no such key exists, return null.

To ensure the tree remains efficient for these operations, the insertion sequence is guaranteed to create a reasonably balanced tree, avoiding worst-case scenarios where the tree degenerates into a linked list. For this problem, you can assume that the k in successor and predecessor queries is guaranteed to be present in the tree at the time of the query.

Format

Input

• The first line contains a single integer $N$ ($1 \leq N \leq 10^5$), representing the number of operations to perform.
• The next $N$ lines each contain an operation, formatted as a string followed by an integer key $k$ ($-10^9 \leq k \leq 10^9$). The string will be one of ins, find, succ, or pred.

Output

• For each find operation, print true or false on a new line.
• For each succ or pred operation, print the integer value of the successor or predecessor on a new line. If one does not exist, print null.
• The ins operation should not produce any output.

Samples

5
ins 10
ins 5
ins 15
find 5
find 6

true
false

Explanation: After the three insertion operations (ins 10, ins 5, ins 15), the BST will have the following structure:

  10
 /  \
5    15

• find 5: The key 5 exists in the tree as the left child of the root. So, the output is true.
• find 6: The key 6 does not exist. A search would go from 10 to 5, and since 6 > 5 and 5 has no right child, the search fails. So, the output is false.

13
ins 50
ins 30
ins 70
ins 20
ins 40
find 60
ins 60
ins 80
find 60
succ 40
pred 60
pred 20
succ 80

false
true
50
50
null
null

Explanation:

1. The first five ins operations build an initial tree. The first find 60 is executed on this tree. Since 60 has not been inserted yet, the output is false.
2. After inserting 60 and 80, the final tree structure for the remaining queries is:

      50
     /  \
    30   70
   / \   / \
 20  40 60  80

3. find 60: Now 60 exists in the tree. The output is true.
4. succ 40: The smallest key in the tree greater than 40 is 50. The output is 50.
5. pred 60: The largest key in the tree smaller than 60 is 50. The output is 50.
6. pred 20: The smallest key in the tree is 20. There is no key smaller than 20. The output is null.
7. succ 80: The largest key in the tree is 80. There is no key greater than 80. The output is null.

13
ins 50
ins 30
ins 70
ins 20
ins 40
find 60
ins 60
ins 80
find 60
succ 40
pred 60
pred 0
succ 80
succ 79

false
true
50
50
null
null
80

Hint

• A solution with $O(N^2)$ overall complexity will be too slow. Since the tree is guaranteed to be reasonably balanced, each operation should ideally take about $O(\log M)$ time, where $M$ is the current number of nodes in the tree.
• The test cases are structured as follows to help you incrementally build and test your solution:
  • Test Cases 1-5: Small-scale inputs with only ins and find operations to check basic tree construction and search logic.
  • Test Cases 6-10: Large-scale inputs ($N$ up to $10^5$) with only ins and find operations. These cases will test the efficiency of your insertion and search algorithms.
  • Test Cases 11-20: Full-scale test cases including all four operations (ins, find, succ, pred) to test the correctness and efficiency of your complete implementation.

Limitation

1s, 128MiB for each test case.