Algorithms and Data Structures

Maximum node in a Binary Search Tree

Given an empty binary search tree with no nodes, you are asked to perform 3 kinds of queries:
  1. insert x - insert the value x in the BST
  1. max - print the maximum value in the BST
  1. print - print the BST in the in-order traversal order.
Given q queries, you are asked to write a program to perform these queries.

Input

The first line of the input contains a single number q (1 ≤ q ≤ 1000).
The next q lines contain queries. For all the insert queries the value of x does not exceed in absolute value.

Output

For each max query, the program should print the maximum value of the BST on a separate line.
For each print query, the program should print the post-order traversal of the BST, where the values should be separated by a space.

Examples

Input
Output
7 insert 2 insert 1 max insert 0 max insert 4 print
2 2 0 1 4 2
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue