BSTでk番目に小さい値を探す

空の二分探索木 (Binary Search Tree、BST) が与えられた状態から、次の2種類のクエリを処理する必要があります:

1. insert x - BSTに値xを挿入する

2. smallest k - BSTの中でk番目に小さい要素を出力する

クエリの総数としてqが与えられるので、これらのクエリを処理するプログラムを作成してください。

入力

最初の行には、整数 q (1 ≤ q ≤ 1000) が与えられます。

続く q 行にはクエリが書かれています。

出力

各 smallest クエリに対して、BSTの中でk番目に小さい要素を出力してください。

例