#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using std::pair;
using std::make_pair;

const int PLUS_INF = 0x7fffffff;
//    7    f    f    f    f    f    f    f
// 0111 1111 1111 1111 1111 1111 1111 1111
// 1000 0000 0000 0000 0000 0000 0000 0000
//    8    0    0    0    0    0    0    0
const int MINUS_INF = 0x80000000;

int cmmdc(int a, int b) {
  if (b == 0) {
    return a;
  } else {
    return cmmdc(b, a % b);
  }
}

int cmmmc(int a, int b) {
  return a * b / cmmdc(a, b);
}

int cmmmc(int a, int b, int c) {
  return cmmmc(a, cmmmc(b, c));
}

struct Node {
  int value;
  int priority; // Min Heap
  int size;
  int sum;
  int cmmmc;
  Node* left;
  Node* right;
};

Node* emptyNode = new Node{0, PLUS_INF, 0, 0, 1, nullptr, nullptr};

Node* makeLeaf(int value, int priority) {
  return new Node{
    value,
    priority,
    1,
    value,
    value,
    emptyNode,
    emptyNode};
}

Node* makeNode(Node* root, Node* left, Node* right) {
  //*root = Node{ // non-persistence
  root = new Node{ // persistence
    root->value,
    root->priority,
    left->size + 1 + right->size,
    left->sum + root->value + right->sum,
    cmmmc(left->cmmmc, right->cmmmc, root->value),
    left,
    right};
  return root;
}

Node* join(Node* first, Node* second) {
  if (first == emptyNode)
    return second;
  else if (second == emptyNode)
    return first;
  else if (first->priority < second->priority) {
    return makeNode(first,
        first->left,
        join(first->right, second));
  } else {
    return makeNode(second,
        join(first, second->left),
        second->right);
  }
}

pair<Node*, Node*> split(Node* root, int value) {
  if (root == emptyNode) {
    return make_pair(emptyNode, emptyNode);
  } else if (value <= root->value) {
    pair<Node*, Node*> tmp = split(root->left, value);
    return make_pair(
       tmp.first,
       makeNode(root, tmp.second, root->right)
    );
  } else {
    pair<Node*, Node*> tmp = split(root->right, value);
    return make_pair(
       makeNode(root, root->left, tmp.first),
       tmp.second
    );
  }
}

bool find(Node* root, int value) {
  if (root == emptyNode)
    return false;
  else if (root->value == value)
    return true;
  else if (value < root->value)
    return find(root->left, value);
  else
    return find(root->right, value);
}

Node* insert(Node* root, Node* node) {
  if (node->priority < root->priority) {
    pair<Node*, Node*> tmp = split(root, node->value);
    return makeNode(node, tmp.first, tmp.second);
  } else if (node->value < root->value) {
    return makeNode(
        root,
        insert(root->left, node),
        root->right);
  } else { // if (root->value < node->value)
    return makeNode(
        root,
        root->left,
        insert(root->right, node));
  }
}

Node* insert(Node* root, int value) {
  if (!find(root, value)) {
    int priority = rand();
    return insert(root, makeLeaf(value, priority));
  } else {
    return root;
  }
}

Node* erase(Node* root, int value) {
  if (root == emptyNode)
    return root;
  else if (root->value == value)
    return join(root->left, root->right);
  else if (value < root->value)
    return makeNode(root,
        erase(root->left, value),
        root->right);
  else
    return makeNode(root,
        root->left,
        erase(root->right, value));
}

void printSpaces(int size) {
  if (size > 0) {
    printf(" ");
    printSpaces(size - 1);
  }
}

void dump(Node* root, int depth = 0) {
  if (root != emptyNode) {
    dump(root->left, depth + 1);
    printSpaces(depth);
    printf("%2d\t%10d\t%2d\t%2d\n",
        root->value,
        root->priority,
        root->size,
        root->sum);
    dump(root->right, depth + 1);
  }
}

Node* queryInterval(Node* root, int left, int right) {
  pair<Node*, Node*> tmp = split(root, left);
  tmp = split(tmp.second, right + 1);
  return tmp.first;
}

int main(void) {
  srand(time(NULL));
  Node* root1 = emptyNode;
  Node* root2 = insert(root1, 5);
  Node* root3 = insert(root2, 3);
  Node* root4 = insert(root3, 7);
  Node* root5 = insert(root4, 4);
  Node* root6 = insert(root5, 9);
  Node* root7 = insert(root6, 2);
  Node* root8 = insert(root7, 1);
  Node* root9 = insert(root8, 6);
  Node* root10 = erase(root9, 4);
  dump(root1);
  printf("\n");
  dump(root2);
  printf("\n");
  dump(root3);
  printf("\n");
  dump(root4);
  printf("\n");
  dump(root5);
  printf("\n");
  dump(root6);
  printf("\n");
  dump(root7);
  printf("\n");
  dump(root8);
  printf("\n");
  dump(root9);
  printf("\n");
  dump(root10);
  printf("\n");
  printf("%d\n", queryInterval(root10, 5, 7)->cmmmc);
  return 0;
}