Новая операционная система
Новая операционная система
Рафаэль разработал новую операционную систему. В ней новый файл создается двумя способами: скопировать ранее созданный файл и добавить к нему какое-то число, или скопировать ранее созданный файл и удалить из него последнее число. Если копируемый файл пустой и к нему применяется операция удаления, то в таком случае создается снова пустой файл.
В самом начале в операционной системе, созданной Рафаэлем, имеется один пустой файл "root". Файл "root" имеет номер 0.
Рафаэль хочет создавать файлы по порядку. i-ый файл может быть создан одним из двух способов:
"push id x" - создается копия файла с номером id (id < i) и к новому файлу в конец добавляется число x (0 ≤ x ≤
10^9
). Выведите количество чисел в новом созданном файле (он имеет номер i)."pop id" - создается копия файла с номером id (id < i) и из нового файла удаляется последнее число (если оно имеется). Выведите удаленное число (или "-1" если такого числа не существует).
Вхідні дані
В первой строке дано количество n (1 < n ≤ 3 * 10^5
) создаваемых файлов. Следующие строки содержат способы создания файлов: i-ая строка описывает один из двух способов создания i-ого файла.
Вихідні дані
Каждый раз при создании нового файла выведите требуемый результат.
Приклад
5 push 0 10 push 1 3 pop 1 push 3 7 pop 3
1 2 10 1 -1
6 push 0 3 push 0 9 push 2 5 pop 2 pop 2 pop 4
1 1 2 9 9 -1