#include <cstdio>
#include <cstdint>

struct Node {
  uint32_t value;
  Node* parent;
  Node* children[2];

  Node() { parent = children[0] = children[1] = nullptr; }
  ~Node() { for (auto p : children) if (p) delete p; }
};

inline void link(Node* p, Node* c, int dir) {
  p->children[dir] = c;
  if (c) c->parent = p;
}

struct Splay {
  Node* root = nullptr;

  ~Splay() { if (root) delete root; }

  inline void rotate(Node* p, Node* c) {
    Node* g = p->parent;
    int dir = p->children[0] == c ? 0 : 1;
    Node* t = c->children[dir ^ 1];

    link(p, t, dir);
    link(c, p, dir ^ 1);

    if (!g) {
      root = c;
      c->parent = nullptr;
    } else {
      int dir = g->children[0] == p ? 0 : 1;
      link(g, c, dir);
    }
  }

  void splay(Node* c) {
    for (;;) {
      Node* p = c->parent;
      if (!p) break;

      Node* g = p->parent;
      if (!g) {
        rotate(p, c);
        break;
      }

      if ((g->children[0] == p) == (p->children[0] == c)) {
        rotate(g, p);
        rotate(p, c);
      } else {
        rotate(p, c);
        rotate(g, c);
      }
    }
  }

  void insert(uint32_t value) {
    Node* n = new Node;
    n->value = value;

    if (!root) {
      root = n;
      return;
    }

    Node* p = root;
    for (;;) {
      int dir = value < p->value ? 0 : 1;
      Node* c = p->children[dir];

      if (!c) {
        link(p, n, dir);
        splay(n);
        break;
      }
      p = c;
    }
  }
};

int main() {
    uint32_t num = 1;
    Splay splay;
    for (int i = 0; i < 1000000; ++i) {
        num = num * 17 + 255;
        splay.insert(num);
    }
    return 0;
}