#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;

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

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

Node* makeLeaf(int value, int priority) {
  return new Node{
    value,
    priority,
    1,
    value,
    0,
    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,
    0,
    left,
    right};
  return root;
}

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

Node* propagate(Node* root) {
  if (root->addition != 0) {
    //*root = Node{ // non-persistence
    root = new Node{ // persistence
      root->value + root->addition,
      root->priority,
      root->size,
      root->sum + root->size * root->addition,
      0,
      addAgregate(root->left, root->addition),
      addAgregate(root->right, root->addition)};
  }
  return root;
}

Node* join(Node* first, Node* second) {
  first = propagate(first);
  second = propagate(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 sizeFirst) {
  //assert(0 <= sizeFirst);
  root = propagate(root);
  if (root == emptyNode) {
    return make_pair(emptyNode, emptyNode);
  } else if (sizeFirst <= root->left->size) {
    pair<Node*, Node*> tmp = split(root->left, sizeFirst);
    return make_pair(
       tmp.first,
       makeNode(root, tmp.second, root->right)
    );
  } else {
    pair<Node*, Node*> tmp = split(root->right, sizeFirst - root->left->size - 1);
    return make_pair(
       makeNode(root, root->left, tmp.first),
       tmp.second
    );
  }
}


int find(Node* root, int index) {
  //assert(0 <= index && index < root->size);
  root = propagate(root);
  if (root == emptyNode)
    return PLUS_INF;
  else if (index < root->left->size)
    return find(
        root->left,
        index);
  else if (index == root->left->size)
    return root->value;
  else // if (index > root->left->size)
    return find(
        root->right,
        index - 1 - root->left->size);
}

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

Node* insert(Node* root, int index, int value) {
  int priority = rand();
  return insert(root, index, makeLeaf(value, priority));
}

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

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\t%5d\n",
        root->value,
        root->priority,
        root->size,
        root->sum,
        root->addition);
    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 propagate(tmp.first);
}

Node* updateInterval(Node* root, int left, int right, int addition) {
  pair<Node*, Node*> tmp1 = split(root, left);
  pair<Node*, Node*> tmp2 = split(tmp1.second, right + 1);
  tmp2.first = addAgregate(tmp2.first, addition);
  tmp1.second = join(tmp2.first, tmp2.second);
  return join(tmp1.first, tmp1.second);
}

int main(void) {
  srand(time(NULL));
  Node* root1 = emptyNode;
  Node* root2 = insert(root1, 0, 8);
  Node* root3 = insert(root2, 1, 5);
  Node* root4 = insert(root3, 1, 4);
  Node* root5 = insert(root4, 2, 7);
  Node* root6 = insert(root5, 2, 6);
  Node* root7 = insert(root6, 0, 9);
  Node* root8 = insert(root7, 6, 3);
  Node* root9 = erase(root8, 3);
  Node* root10 = erase(root9, 3);
  Node* root11 = updateInterval(root8, 1, 4, 3);
  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, 2, 4)->sum);
  dump(root11);
  printf("\n");
  return 0;
}