Nodo massimo in un Binary Search Tree (albero binario di ricerca)

Dato un Binary Search Tree (BST) inizialmente vuoto e senza nodi, ti viene chiesto di eseguire 3 tipi di query:

1. insert x – inserisce il valore x nel BST

2. max – stampa il valore massimo presente nel BST

3. print – stampa il contenuto del BST nell'ordine di visita in-order

Dato un numero q di query, devi scrivere un programma che le esegua tutte.

Input

La prima riga dell’input contiene un solo numero q (1 ≤ q ≤ 1000).

Le successive q righe contengono le query da eseguire. Per tutte le query insert, il valore di x non supera 10^9 in valore assoluto.

Output

Per ogni query max, il programma deve stampare su una nuova riga il valore massimo del BST.

Per ogni query print, il programma deve stampare il BST in visita post-order, inserendo uno spazio fra i vari valori.

Esempi