题意

有空序列 \(a\)，另外有 \(10^9\) 个空序列 \(p1 \sim p_{10^9}\)，现在执行 \(q\) 次操作，包括以下四种操作：
- ADD x，在序列 \(a\) 后插入整数 \(x\)。
- DELETE，删除 \(a\) 的末尾元素，空则什么都不干。
- SAVE y，赋值操作，\(p_x = a\)。
- LODE z，将 \(a\) 变为 \(p_z\)。
每次操作后输出 \(a\) 的末尾元素，没有输出 \(-1\)。
数据范围：\(1 \le q \le 5 \times 10^5, 1 \le x,y,z \le 10^9\)。

思路

显然有一个暴力，模拟操作，肯定超时。
首先我们肯定不能把整个序列存下来，但是有些元素删除了，\(LODE\) 后可能又恢复了，那该怎么办呢？
我们可以考虑一个树形结构，令 \(nx\) 为当前 \(a\) 的末尾元素，\(pos_y\) 表示 \(p_y\) 的末尾元素，那么插入元素就是将 \(fa_x = nx, nx = x\)，删除就是 \(nx = fa_{nx}\)，第三种操作，就是将 \(pos_y = nx\)，最后一种就是 \(nx = pos_z\)。