!Персистентное Декартово Дерево

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double ld;

#define fastRead cin.sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define fi first
#define se second

struct Node
{
    int x;
    ll sum;
    int size;
    Node *left;
    Node *right;
    Node(int x):
        x(x),
        sum(x),
        size(1),
        left(0),
        right(0) {}
};

int size(Node *v)
{
    return (v == NULL ? 0 : v->size);
}

ll sum(Node *v)
{
    return (v == NULL ? 0 : v->sum);
}

void upd(Node *v)
{
    if (!v)
        return;
    v->sum = v->x + sum(v->left) + sum(v->right);
    v->size = 1 + size(v->left) + size(v->right);
}

pair<Node*, Node*> split(Node *v, int s)
{
    if (!v)
        return {v, v};
    if (!s)
        return {0, v};
    Node *t = new Node(v->x);
    if (size(v->left) >= s)
    {
        pair<Node*, Node*> a = split(v->left, s);
        t->left = a.second;
        t->right = v->right;
        upd(t);
        return {a.first, t};
    }
    pair<Node*, Node*> a = split(v->right, s - 1 - size(v->left));
    t->right = a.first;
    t->left = v->left;
    upd(t);
    return {t, a.second};
}

pair<Node*, Node*> split1(Node *v, int s)
{
    if (!v)
        return {v, v};
    if (!s)
        return {0, v};
    if (size(v->left) >= s)
    {
        pair<Node*, Node*> a = split1(v->left, s);
        v->left = a.second;
        upd(v);
        return {a.first, v};
    }
    pair<Node*, Node*> a = split1(v->right, s - 1 - size(v->left));
    v->right = a.first;
    upd(v);
    return {v, a.second};
}

Node* merge(Node *l, Node *r)
{
    if (!l)
        return r;
    if (!r)
        return l;
    int a = (rand() << 16) + rand();
    a %= (size(l) + size(r));
    if (a < size(l))
    {
        Node *L = new Node(l->x);
        Node *q = merge(l->right, r);
        upd(q);
        L->left = l->left;
        L->right = q;
        upd(L);
        return L;
    }
    Node *R = new Node(r->x);
    Node *q = merge(l, r->left);
    upd(q);
    R->right = r->right;
    R->left = q;
    upd(R);
    return R;
}

Node* merge1(Node *l, Node *r)
{
    if (!l)
        return r;
    if (!r)
        return l;
    int a = (rand() << 16) + rand();
    a %= (size(l) + size(r));
    if (a < size(l))
    {
        Node *q = merge1(l->right, r);
        upd(q);
        l->right = q;
        upd(l);
        return l;
    }
    Node *q = merge1(l, r->left);
    upd(q);
    r->left = q;
    upd(r);
    return r;
}

void gogo(Node *v)
{
    if (!v)
        return;
    gogo(v->left);
    cout << v->x << " ";
    gogo(v->right);
}

int main()
{
    in("memory.in");
    out("memory.out");
    fastRead;
    int n;
    cin >> n;
    ll x, a, b, m;
    cin >> x >> a >> b >> m;
    Node *root = new Node(x);
    for (int i = 2; i <= n; i++)
    {
        x = (x * a + b) % m;
        root = merge1(root, new Node(x));
    }
    int k;
    cin >> k;
    for (int i = 0; i < k; i++)
    {
        string s;
        cin >> s;
        if (s == "sum")
        {
            int l, r;
            cin >> l >> r;
            auto a = split(root, r);
            auto b = split(a.first, l - 1);
            cout << sum(b.second) << "\n";
            root = merge(b.first, merge(b.second, a.second));
        }
        else if (s == "out")
        {
            int l, r;
            cin >> l >> r;
            auto a = split(root, r);
            auto b = split(a.first, l - 1);
            gogo(b.second);
            root = merge(b.first, merge(b.second, a.second));
            cout << "\n";
        }
        else
        {
            int aa, bb, l;
            cin >> aa >> bb >> l;
            auto a = split(root, aa - 1);
            auto b = split(a.second, l);
            a = split(root, bb - 1);
            auto c = split(a.second, l);
            root = merge(a.first, merge(b.first, c.second));
        }
    }
    return 0;
}