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

Рафаель розробив нову операційну систему. У ній новий файл можна створити двома способами: скопіювати раніше створений файл і додати до нього певне число, або скопіювати раніше створений файл і видалити з нього останнє число. Якщо копійований файл порожній і застосовується операція видалення, то створюється знову порожній файл.

На початку в операційній системі, створеній Рафаелем, є один порожній файл "root". Файл "root" має номер 0.

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

1. "push id x" - створюється копія файлу з номером id (id < i) і до нового файлу в кінець додається число x (0 ≤ x ≤ 10^9). Виведіть кількість чисел у новоствореному файлі (він має номер i).

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

Вхідні дані

У першому рядку задано кількість n (1 < n ≤ 3 * 10^5) створюваних файлів. Наступні рядки містять способи створення файлів: i-ий рядок описує один з двох способів створення i-ого файлу.

Вихідні дані

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

Приклади