Implementa un almacén que guarda varios valores para una misma clave, cada uno con su instante de tiempo:

• set k v t: guarda el valor \(v\) para la clave \(k\) en el instante \(t\).
• get k t: imprime el valor guardado para \(k\) con el mayor instante que sea \(\le t\). Si no hay ninguno, imprime -.

Los instantes de los set son estrictamente crecientes a lo largo de toda la entrada.

Entrada

La primera línea tiene \(q\) \((1 \le q \le 10^5)\) y siguen \(q\) líneas con una operación cada una. Claves y valores son palabras de entre \(1\) y \(10\) caracteres (letras minúsculas y dígitos), y \(1 \le t \le 10^7\).

Salida

Una línea por cada get, con su respuesta.

Ejemplo 1

Entrada

5
set foo bar 1
get foo 1
get foo 3
set foo bar2 4
get foo 4

Salida

bar
bar
bar2

Ejemplo 2

Entrada

4
get a 5
set a x 10
get a 9
get a 10

Salida

-
-
x

Basado en el problema 981 de LeetCode, Time Based Key-Value Store, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.