Splay Tree

#include <bits/stdc++.h>

using namespace std;

#define llong long long int

template<typename T>
struct RandomNumberGenerator {
private:
    int cnt;
    T S, A, C, last;

public:
    RandomNumberGenerator(T S, T A, T C): S(S), A(A), C(C), cnt(0) {}

    T next() {
        if (cnt++ == 0) return last = S;
        return last = A * last + C;
    }
};

template<typename T>
struct SplayTree {
private:
    struct Node {
        T v;
        Node *l, *r, *p;

        Node(T v, Node *l = NULL, Node *r = NULL, Node *p = NULL): v(v), l(l), r(r), p(p) {}
    };

    Node *root;

public:
    SplayTree(): root(NULL) {}

    int insert(T v) {
        int depth = 0;
        root = insert(root, v, depth);
        return depth;
    }

    int query(T v) {
        int depth = 0;
        root = splay(query(root, v, depth));
        return depth;
    }

private:
    Node* insert(Node *node, T v, int &depth) {
        if (node == NULL) return new Node(v);
        if (node->v == v) {
            depth = -1;
            return node;
        }

        depth++;
        if (v < node->v) {
            node->l = insert(node->l, v, depth);
            node->l->p = node;
        } else {
            node->r = insert(node->r, v, depth);
            node->r->p = node;
        }

        return node;
    }

    Node *query(Node *node, T v, int &depth) {
        if (node == NULL) {
            depth = -1;
            return NULL;
        }

        if (node->v == v) return node;

        depth++;
        if (v < node->v) return query(node->l, v, depth);
        return query(node->r, v, depth);
    }

    void rotate_left(Node *node) {
        node->p->r = node->l;
        if (node->l != NULL)
            node->l->p = node->p;

        node->l = node->p;
        if (node->p->p != NULL) {
            if (node->p->p->l == node->p) node->p->p->l = node;
            else node->p->p->r = node;
        }

        node->p = node->p->p;
        node->l->p = node;
    }

    void rotate_right(Node *node) {
        node->p->l = node->r;
        if (node->r != NULL)
            node->r->p = node->p;

        node->r = node->p;
        if (node->p->p != NULL) {
            if (node->p->p->l == node->p) node->p->p->l = node;
            else node->p->p->r = node;
        }

        node->p = node->p->p;
        node->r->p = node;
    }

    void zig(Node *node) {
        if (node->p->l == node) rotate_right(node);
        else rotate_left(node);
    }

    Node* splay(Node *node) {
        if (node == NULL) return root;

        while (node->p != NULL && node->p->p != NULL) {
            if ((node->p->l == node && node->p->p->l == node->p) || (node->p->r == node && node->p->p->r == node->p)) {
                zig(node->p);
                zig(node);
            } else {
                zig(node);
                zig(node);
            }
        }

        while (node->p != NULL)
            zig(node);

        return node;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    const uint32_t A = 1664525;
    const uint32_t C = 1013904223;

    uint32_t S;
    int U, B, N, I, Q, P;
    cin >> S >> U >> B >> N >> I >> Q >> P;

    RandomNumberGenerator<uint32_t> rng(S, A, C);

    SplayTree<uint32_t> T;
    while (B--)
        T.insert(rng.next() % U);

    for (int i = 0; i < N; i++) {
        uint32_t X = rng.next();
        uint32_t K = rng.next() % U;

        bool ins = X % (I + Q) < I;
        int D = ins ? T.insert(K) : T.query(K);
        if (i % P == 0)
            cout << (ins ? "I" : "Q") << " " << K << " " << D << "\n";
    }
}