Нова операційна система#9031
Рафаель розробив нову операційну систему. У ній новий файл можна створити двома способами: скопіювати раніше створений файл і додати до нього певне число, або скопіювати раніше створений файл і видалити з нього останнє число. Якщо копійований файл порожній і застосовується операція видалення, то створюється знову порожній файл.
На початку в операційній системі, створеній Рафаелем, є один порожній файл root. Файл root має номер .
Рафаель хоче створювати файли по порядку. -й файл може бути створений одним з двох способів:
"push id x" — створюється копія файлу з номером (id < i) і до нового файлу в кінець додається число (0 \leq x \leq 10^9). Виведіть кількість чисел у новоствореному файлі (він має номер ).
"pop id" — створюється копія файлу з номером (id < i) і з нового файлу видаляється останнє число (якщо воно є). Виведіть видалене число (або "-1", якщо такого числа не існує).
У першому рядку задано кількість (1 < n \leq 3 \cdot 10^5) створюваних файлів. Наступні рядків містять способи створення файлів: -й рядок описує один з двох способів створення -го файлу.
Кожного разу при створенні нового файлу виведіть потрібний результат.
Приклад 65
Приклад 66