29650번 - Княжества 다국어

문제

Лествичное право (от старо-славянского <<лествица>> - лестница) - обычай великокняжеского наследования в Киевской Руси.

В великом государстве Эн правил мудрый правитель Эм. У мудрого правителя Эм было несколько сыновей. И чтобы каждый из сыновей вырос хорошим правителем, решил Эм каждому выделить по княжеству великому в управление. Но не все княжества равны между собой были, ибо часть была в плодородных землях черноземных, часть в лесах темных, часть в степях диких, да и по размеру княжества были различны. Задумался мудрый Эм, и порешил занумеровать все княжества в порядке главенства -- самое главное княжество нарек он Первым, следующее -- Вторым, и так далее. И княжеств в Энском государстве было бесчисленное множество, и каждое свой номер имело. Старшему наследнику отдал Эм Первое княжество. И Второму своему сыну отдал он Второе княжество, и так далее.

Но тут родилися у Эм внуки, и снова задумался мудрый правитель. Ибо внукам надлежало тоже быть хорошими правителями, а значит и им надобно было выделить княжества. И порешил Эм, что выделит он всем внукам по княжеству, но не в порядке старшинства, а иначе -- сперва лучшие княжества среди сыновей в порядке старшинства распределяются, затем следующие княжества сыновьям старшего брата в правление отдаются, также по старшинству распределенные, потом второго брата сыновьям, по старшинству, и так далее. И обрадовался Эм, ибо система такая позволяла и правнукам, и всем прочим потомкам мужеского пола выделять княжества в правление, и по главенству княжества верно распределены были. И когда родился у Эм еще один сын, то все внуки его и правнуки, и остальные потомки мужеского пола править стали княжеством с на единицу большим номером, а сын новорожденный стал править княжеством с номером на единицу большим чем у второго по младшинству сына, ибо никакой внук не правил княжеством более главным, чем каждый из сыновей, а среди сыновей порядок главенства старшинством задается.

Но тут печаль у Эм приключилась. Умер сын его, и великое княжество без правителя осталось. И призадумался Эм, и решил, что если погиб потомок, то княжество, без правителя оставшееся, правитель следующего княжества княжить будет. Так, все следующие потомки мужекого пола станут княжить земли с на единицу меньшим номером, и все княжества верно по главенству распределены будут.

Получилось так, что в великом государстве в каждый момент времени есть порядок на князях, задаваемый следующим образом: сначала правитель Эм, потом его сыновья в порядке старшинства, потом сыновья старшего сына также в порядке старшинства, потом аналогично сыновья второго по старшинству сына Эма и так далее вплоть до самого младшего.

Таким образом, любой князь из более позднего поколения идет после любого князя из более младшего (даже, если первый старше). Например, любой правнук идет после любого внука.

Летописец государства Эн прилежно вел запись всех событий государства, всех смертей и рождений, в хронологическом порядке. В ваши руки попала эта бесценная летопись. Требуется написать программу для обработки этой летописи, которая будет способна определять, кто правит в $k$-ом княжестве в определенные моменты времени?

입력

В первой строчке содержится единственное число $n$ --- количество событий и запросов в государстве великом (1ドル \le n \le 2000$). Следующие строки содержат описания событий в государстве великом и запросов о том, кто в каком княжестве княжит по одному событию или запросу в строчке и в порядке происшествия данных событий в следующем формате:

• строка вида <<+ Father Son>> сообщает о великом событии, что у князя с именем <<Father>> родился сын, которого он нарек <<Son>>;
• строка вида <<- Name>> сообщает о великом горе, что умер князь, нареченный <<Name>>;
• строка вида <<? k>> есть суть вопрос --- кто в данный момент княжит в $k$-ом по главенству княжестве (1ドル \le k \le 2500$).

Никакие два князя за все время существования государства не имели одинаковых имен и все имена князей в летописи данной записаны только строчными и заглавными латинскими буквами и имеют длину не более 20 символов.

Летопись началась вестись в тот момент, когда в государстве жил один единственный мудрый правитель, именовали которого <<M>>, то есть просто Эм, и правил он в Первом княжестве.

출력

На каждый запрос вида <<? k>> в выходной файл выведите по одной строке, содержащей имя князя, правившего на момент запроса в $k$-ом по главенству княжестве, или единственный символ <<->>, если на момент запроса в $k$-ом княжестве нет правителя, ибо нет такого количества живых князей.

Все ответы выводите на запросы в том порядке, в котором они задаются во входном файле.

제한

힌트