e-olymp
Соревнования

IOI 2019 Azerbaijan Team Selection Contest (Day1 + Day2)

Новая операционная система

Рафаэль разработал новую операционную систему. В ней новый файл создается двумя способами: скопировать ранее созданный файл и добавить к нему какое-то число, или скопировать ранее созданный файл и удалить из него последнее число. Если копируемый файл пустой и к нему применяется операция удаления, то в таком случае создается снова пустой файл.

В самом начале в операционной системе, созданной Рафаэлем, имеется один пустой файл "root". Файл "root" имеет номер 0.

Рафаэль хочет создавать файлы по порядку. i-ый файл может быть создан одним из двух способов:

1) "push id x" - создается копия файла с номером id (id < i) и к новому файлу в конец добавляется число x (0x109). Выведите количество чисел в новом созданном файле (он имеет номер i).

2) "pop id" - создается копия файла с номером id (id < i) и из нового файла удаляется последнее число (если оно имеется). Выведите удаленное число (или "-1" если такого числа не существует).

Входные данные

В первой строке дано количество n (1 < n3 * 105) создаваемых файлов. Следующие строки содержат способы создания файлов: i-ая строка описывает один из двух способов создания i-ого файла.

Выходные данные

Каждый раз при создании нового файла выведите требуемый результат.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #65
5
push 0 10
push 1 3
pop 1
push 3 7
pop 3
Выходные данные #65
1
2
10
1
-1
Входные данные #66
6
push 0 3
push 0 9
push 2 5
pop 2
pop 2
pop 4
Выходные данные #66
1
1
2
9
9
-1
Источник 2019 İOİ Отборочный тур сборной Азербайджана