let read_int() = Scanf.scanf " %d" (fun x-> x);;

type tree =
    | Nil
    | Noeud of tree * int * tree * int * int * string

let hauteur = function
    | Nil -> 0
    | Noeud(_,_,_,h, _, _) -> h

let taille = function
    | Nil -> 0
    | Noeud(_, _, _, _, n, _) -> n

let indice = function
    | Nil -> 0
    | Noeud(g, _, _, _, _, _) -> 1 + taille g

let desequilibre = function
    | Nil -> 0
    | Noeud(g, _, d, _, _, _) -> hauteur g - hauteur d

let update_hauteur = function
    | Nil -> Nil
    | Noeud(g, x, d, _, t, s) -> Noeud(g, x, d, 1 + max (hauteur g) (hauteur d), t, s)

let update_taille = function
    | Nil -> Nil
    | Noeud(g, x, d, h, _, s) -> Noeud(g, x, d, h, 1 + taille g + taille d, s)

let update = function
    | Nil -> Nil
    | Noeud(g, x, d, _, _, s) -> update_hauteur (update_taille (Noeud(g, x, d, -1, -1, s)))


let rotation_droite = function
    | Nil -> failwith "Structure incorrecte 1 !"
    | Noeud(Nil, _, _, _, _, _) -> failwith "Structure incorrecte 2 !"
    | Noeud( Noeud(t1, y, t2, _, _, s), x, t3, _, _, t) ->
        let new_x = update (Noeud(t2, x, t3, -1, -1, t)) in
        update (Noeud(t1, y, new_x, -1, -1, s))

let rotation_gauche = function
    | Nil -> failwith "Structure incorrecte 3 !"
    | Noeud(_, _, Nil, _, _, _) -> failwith "Structure incorrecte 4 !"
    | Noeud(t1, x, Noeud(t2, y, t3, _, _, s ), _, _, t) ->
        let new_x = update (Noeud(t1, x, t2, -1, -1, t)) in
        update (Noeud(new_x, y, t3, -1, -1, s))

let equilibre tree = match desequilibre tree with
    | n when n < -1 -> rotation_gauche tree
    | n when n > 1 -> rotation_droite tree
    | n -> update tree

let rec insere x s = function
    | Nil -> Noeud(Nil, x, Nil, 0, 1, s)
    | Noeud(l, y, r, _, _, t) when x < y -> equilibre (Noeud(insere x s l, y, r, -1, -1, t))
    | Noeud(l, y, r, _, _, t) -> equilibre (Noeud(l, y, insere x s r, -1, -1, t))

let rec kth k = function
    | Nil -> failwith "Arbre trop petit"
    | Noeud(g, x, d, _, _, s) when k = 1+taille g -> s
    | Noeud(g, x, d, _, _, _) when k < 1+taille g-> kth k g
    | Noeud(g, x, d, _, _, _)             -> kth (k-1 - (taille g)) d


let main () =
    let nb_canards = read_int () in
    let tree = ref Nil in

    for i = 0 to (nb_canards-1) do
        let nom = Scanf.scanf " %s" (fun x -> x) in
        let pos = read_int() in
        let k = read_int() in
        tree := insere pos nom !tree;
        print_string (kth k !tree);
        print_char '\n'
    done;
    ()

let t = main ()