伽利略·伽利莱（Galileo Galilei）是一位著名的天文学家。他是第一位使用望远镜观测天空的人。他发现了许多天体，但要记住所有这些天体似乎相当困难……

有传言说，他发明了一种用于追踪其发明和发现的系统，称为“伽利略发明追踪器”（Galilei’s inventions tracker），简称 git。它允许保存各种信息的多个版本。例如，如果你想查看几个月前观测到的某颗恒星的参数，只需查询该系统即可。你的任务是复现该追踪器简化版本的行为。简要描述如下。

一个 commit（提交）代表了整个系统状态。提交以从 0 开始的连续整数命名。最初，只有编号为 0 的提交。提交构成了一棵以 0 为根的有根树：除了根节点外，每个提交都有且仅有一个父节点。如果可以从 $b$ 出发，通过多次向上移动到父节点到达 $a$，则称 $a$ 是 $b$ 的一个 ancestor（祖先）。始终有一个提交被选为 working copy（工作副本）。系统支持以下几种操作：

• co x，“checkout”：将提交 $x$ 选为工作副本。
• ci，“commit”：创建一个新的提交，其父节点为当前工作副本，并将其选为工作副本。新提交获得尽可能小的 ID。
• re x，“rebase”：设当前工作副本为 $y$。找到 $x$ 和 $y$ 的最低公共祖先（LCA）$t$。将从 $t$ 到 $y$ 的路径（不包括 $t$）复制到 $x$ 之上。新提交的编号规则如下：首先，最靠近 $x$ 的提交获得尽可能小的编号，然后第二个提交获得下一个尽可能小的编号，依此类推。最后一个被复制的提交成为你的工作副本。

如果 $x$ 是 $y$ 的祖先，则什么都不做，路径也不会被复制。如果 $y$ 是 $x$ 的祖先，则路径不会被复制，且 $x$ 成为工作副本。

你的任务是实现所有这些操作。

输入格式

输入的第一行包含一个整数 $n$ ($0 \leqslant n \leqslant 10^5$)。接下来的 $n$ 行中，每一行包含以下命令之一：

• co x：检出提交 $x$
• ci：提交
• re x：在提交 $x$ 之上进行变基（rebase）

保证提交编号始终有效。此外，保证在所有操作完成后，提交总数不超过 $10^{18}$。

输出格式

在每次 rebase 操作后，输出该操作完成后工作副本提交的编号。

样例

输入 1

7
ci
ci
co 0
ci
ci
re 1
re 4

输出 1

6
9