Zadano je \(n\) linija teksta. Svaka linija počinje s određenim brojem znakova '-' (crtica), nakon čega slijedi ključ. Broj crtica na početku linije označava razinu u hijerarhijskoj strukturi. Linija bez crtica je na najvišoj razini (razina 0). Jedna crtica označava razinu 1, dvije crtice razinu 2, i tako dalje.

Vaš zadatak je transformirati ovaj niz linija u objekt koji predstavlja hijerarhijsku strukturu. Svaki ključ u objektu ili podobjektu odgovara ključu iz ulaznog niza. Struktura se gradi na temelju razina označenih crticama.

Ulazni podatci

U prvom redu nalazi se broj \(n\), broj redova. (\(1 \leq n \leq 10^5\))

U idućih \(n\) redova dobiti ćete string u obliku [broj_crtica]ključ. broj_crtica je nenegativan broj, a ključ neće imati više od 100 znakova. Ključevi se neće ponavljati.

Izlazni podatci

Ispišite traženi objekt iz zadatka.

Podzadatci

Ulaz primjera 1

6
abc
-cc
-bb
-dd
--aaa
-ff

Izlaz primjera 1

{"abc":{"cc":{},"bb":{},"dd":{"aaa":{}},"ff":{}}}

Ulaz primjera 2

5
a
-b
--c
-d
--e

Izlaz primjera 2

{"a":{"b":{"c":{}},"d":{"e":{}}}}