Principalities

Lestvichnoe pravo (from the Old Slavic word "lestvitsa", meaning ladder) is the custom of grand-princely succession in Kievan Rus.

In the great state of En, a wise ruler named Em reigned. Em had several sons. So that each son would grow into a good ruler, Em decided to give each son a grand principality to govern. The principalities were not equal. Some lay on fertile black earth, some in dark forests, some in wild steppes, and their sizes also differed. Em thought carefully and numbered all the principalities by rank. He named the most important principality First, the next one Second, and so on. The state of En had countless principalities, and each had its own number. Em gave the First principality to his eldest heir, the Second to his second son, and so on.

Then grandchildren were born to Em, and the wise ruler thought again. The grandchildren also had to become good rulers, so they needed principalities too. Em decided that every grandchild would get one, but not in order of seniority. Instead, the best principalities among the sons would go first, distributed by seniority among the sons. Then the next principalities would go to the sons of the eldest brother, also distributed by seniority. Then to the sons of the second brother, by seniority, and so on. Em was pleased, because this system let great-grandchildren and all other male descendants receive principalities too, and the principalities stayed correctly ordered by rank. When another son was born to Em, all of his grandchildren, great-grandchildren, and other male descendants began to rule the principality whose number was one larger. The newborn son began to rule the principality whose number was one larger than that of the second youngest son. No grandchild ever ruled a more important principality than any son, because the order among sons is set by seniority.

Then a misfortune struck. Em's son died, and the grand principality was left without a ruler. Em thought it over and decided that if a descendant died, the ruler of the next principality would govern the vacant one. So all the following male descendants would rule the principality whose number was one smaller, and all principalities would stay correctly ordered by rank.

At every moment, the state of En has an order of princes defined as follows: first Em, then his sons in order of seniority, then the sons of the eldest son in order of seniority, then similarly the sons of the second son in order of seniority, and so on down to the youngest son.

So any prince from a later generation comes after any prince from an earlier generation, even if the first one is older. For example, every great-grandson comes after every grandson.

The chronicler of the state of En recorded every event carefully, every death and birth, in chronological order. You have obtained this priceless chronicle. Write a program that processes it and determines who rules the k-th principality at given moments in time.

The first line contains a single integer $n$, the number of events and queries in the state ($1 \le n \le 2000$). Each of the following lines describes one event or query, in the order they occurred. The formats are:

• + Father Son: the prince named Father has a son named Son.
• - Name: the prince named Name has died.
• ? k: who currently rules the k-th principality by rank? ($1 \le k \le 2500$)

No two princes in the whole history have the same name. All names consist only of uppercase and lowercase Latin letters and are at most 20 characters long.

The chronicle begins when one wise ruler, named M (that is, simply Em), lives in the state and rules the First principality.

For each query ? k, print on its own line the name of the prince who rules the k-th principality by rank at that moment. If no living prince can rule the k-th principality at that moment, because there are not that many living princes, print -. Print the answers in the same order as the queries appear in the input.