Maximaler Knoten in einem Binary Search Tree

Ausgehend von einem leeren Binary Search Tree (BST) ohne Knoten sollen Sie drei Arten von Abfragen ausführen:

1. insert x – Fügt den Wert x in den BST ein.

2. max – Gibt den maximalen Wert im BST aus.

3. print – Gibt den BST in In-Order-Reihenfolge aus.

Es wird vorausgesetzt, dass q Abfragen vorliegen. Ihre Aufgabe ist es, ein Programm zu schreiben, das diese Abfragen entsprechend ausführt.

Input

Die erste Zeile der Eingabe enthält eine einzelne Zahl q (1 ≤ q ≤ 1000).

Die nächsten q Zeilen enthalten Abfragen. Bei allen insert-Abfragen überschreitet der Wert x nicht den Betrag .

Output

Für jede max-Abfrage soll das Programm den maximalen Wert des BST in einer eigenen Zeile ausgeben.

Für jede print-Abfrage soll das Programm die Post-Order-Traversierung des BST ausgeben. Die Werte werden dabei durch ein Leerzeichen getrennt.

Examples