長さが \(O(N)\) の文字列のコピーには \(O(N)\) の時間がかかってしまうため、各クエリで指示される操作をそのまま愚直にシミュレーションすることはできません。永続配列などのデータ構造を用いた解法も考えられますが、ここではより実装が簡単な解法を説明します。

簡単のため、以降サーバーのことを PC \(0\) と呼ぶことにします。

前から \(t\) 番目までのクエリを処理し終えた段階での PC \(i\) の文字列を \(f(t, i)\ (0\leq t\leq Q, 0\leq i\leq N)\) と表記します。

各種類のクエリの内容をこの \(f\) を用いて整理すると、以下のようになります。

• 任意の \(t\ (1\leq t\leq Q)\) について、\(t\) 番目のクエリが、
  • 1 p のとき：\(f(t, p)=f(t-1, 0)\)、\(f(t,i)=f(t-1,i)\ (i\neq p)\)
  • 2 p s のとき：\(f(t, p)=f(t-1, p)+s\)、\(f(t,i)=f(t-1,i)\ (i\neq p)\) （ただしここでの \(+\) は文字列の連結を表す）
  • 3 p のとき：\(f(t, 0)=f(t-1, p)\)、\(f(t,i)=f(t-1,i)\ (i\neq 0)\)

今求めたいのは \(f(Q, 0)\) の値ですから、上記の関係式を \(t=Q,Q-1,\dots,1\) の順に繰り返し適応していけば（すなわちクエリを後ろから順に見ていけば）、最終的にはある \(i\) に対する \(f(0, i)\) を求める問題に帰着されます。この問題の答えは空文字列だとわかっていますから、その時点で求値が完了します。

より具体的にアルゴリズムを記述すると、以下の通りです。

1. \(t=Q, i=0,\mathrm{ans}=\) (空文字列) とする。
2. \(\mathrm{query}_t=\) 1 p かつ \(i=p\) ならば、\(i\leftarrow 0\) と更新する。
3. \(\mathrm{query}_t=\) 2 p s かつ \(i=p\) ならば、\(\mathrm{ans}\leftarrow s+\mathrm{ans}\) と更新する。
4. \(\mathrm{query}_t=\) 3 p かつ \(i=0\) ならば、\(i\leftarrow p\) と更新する。
5. \(t\leftarrow t-1\) と更新する。
6. \(t=0\) ならばアルゴリズムを終了する。そうでないならば 2. に戻る。

このアルゴリズムは \(O(Q+\sum |s|)\) 時間で動作します。

実装上の注意：C++ や Python を含む多くの言語では、3. の操作を単に ans = s + ans と実装してしまうと、ans をコピーするコストが余計にかかってしまい、計算量が悪化します。よって、ans の値を管理する代わりに、ans をリバースした文字列 rev(ans) の値を管理し（この場合 3. の操作は rev(ans) += rev(s) と実装できます）、一番最後にもう一度リバースして元の ans の値を求めるとよいです。

実装例 (C++) :

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> op(q), p(q);
    vector<string> s(q);
    for (int i = 0; i < q; i++) {
        cin >> op[i] >> p[i];
        if (op[i] == 2) {
            cin >> s[i];
            reverse(s[i].begin(), s[i].end());
        }
    }

    string ans;
    int i = 0;
    for (int t = q - 1; t >= 0; t--) {
        if (op[t] == 1) {
            if (i == p[t]) {
                i = 0;
            }
        } else if (op[t] == 2) {
            if (i == p[t]) {
                ans += s[t];
            }
        } else {
            if (i == 0) {
                i = p[t];
            }
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
}