Reading and writing entire sequence on the notebook costs so much that it is difficult to fit in the execution time and memory limit. To handle this issue, we describe a way to process the queries fast by storing all the current and past state of \(A\) in a tree.

First, prepare a rooted tree with the only vertex \(r\) with \(-1\) written on it (where the unique vertex \(r\) is the root), and place a piece on vertex \(r\). Then,

• given a query ADD \(x\), add a new vertex \(v\) as a child of the vertex where a piece is currently on, write the integer \(x\) on vertex \(v\), and move the piece to vertex \(v\);
• given a query DELETE, move the piece to the parent of the vertex where the piece is placed. If the piece is on the root, do nothing.

Note that, by performing ADD and DELETE as mentioned above, the current sequence \(x\) is always equal to “the sequence of integers written on the vertices in the simple path from the root to the vertex with the current piece, without the initial \(-1\).” Therefore, when recording current \(A\), it is sufficient to record the current vertex instead of the sequence itself. That is,

• given a query SAVE \(y\), record the (ID or address of) vertex where the piece is currently on on the \(y\)-th page of the notebook. The record on the each page of the notebook can be managed with an associative array.

Additionally,

• given a query LOAD \(z\), refer to the \(z\)-th page of the notebook and move the piece to the vertex written on that page.

The last element of \(A\) always corresponds to the integer written on the vertex where the piece is currently placed on, and even if \(A\) is empty (where the piece is on the root \(r\)), \(-1\) is written on the root, so anyway, in order to solve this problem, it is sufficient to print the integer written on the vertex where the piece is currently placed at every time a query is processed.

The following is a sample code in C++ language.

#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct Node{
  int val, par;
  vector<int> vec;
  Node(int v, int p){val = v, par = p;};
};

int Q;
map<int, int> mp;
vector<Node> vec;

int main(void)
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> Q;
  
  int v = 0;
  vec.push_back(Node(-1, 0));

  string s; int x;
  for(int i = 1; i <= Q; i++){
    cin >> s;
    if(s == "ADD"){
      cin >> x;
      vec.push_back(Node(x, v));
      vec[v].vec.push_back((int)vec.size()-1);
      v = (int)vec.size()-1;
    }
    if(s == "DELETE") v = vec[v].par;
    if(s == "SAVE"){
      cin >> x;
      mp[x] = v;
    }
    if(s == "LOAD"){
      cin >> x;
      v = mp[x];
    }
    cout << vec[v].val << " ";
  }
  cout << endl;
  
  return 0;
}