#include <cstdio>
#include <cinttypes>
#include <cstdlib>
#include <limits>
#include <array>
#include <algorithm>

typedef int64_t num_items;

namespace treap {
    template <class item_key, class item_value> struct treap;

    template <class item_key, class item_value> struct node {
        item_key key;
        item_value value;
        item_key min;
        item_key max;
        num_items priority;
        num_items size;
        treap<item_key, item_value> left;
        treap<item_key, item_value> right;
    };

    template <class item_key, class item_value> struct treap_pair {
        treap<item_key, item_value> left;
        treap<item_key, item_value> right;
        treap_pair() : left(nullptr), right(nullptr) {};
    };

    template <class item_key, class item_value> treap<item_key, item_value> newTreapNode(item_key key, item_value value);

    template <class item_key, class item_value> struct treap {
        node<item_key, item_value> *root;
        treap() { root = nullptr; }
        treap(node<item_key, item_value> *ptr) { root = ptr; }

        template <class item_key_container, class item_value_container> treap(num_items numItems, item_key_container keyArr, item_value_container valueArr) {
            //Return an empty treap if there are no items:
            if (numItems == 0) {
                root = nullptr;
                return;
            }
            //Return a treap with one item if there is an item:
            if (numItems == 1) {
                root = nullptr;
                addElementByKey(*keyArr, *valueArr, false);
                return;
            }

            //Find where the median is located:
            num_items medianPos = numItems/2;
            //Build the left and right sides accordingly:
            treap<item_key, item_value> leftSide(medianPos, keyArr, valueArr);
            treap<item_key, item_value> rightSide(numItems-medianPos, keyArr+medianPos, valueArr+medianPos);
            //Merge the two treaps together:
            root = mergeTreaps(leftSide, rightSide).root;
        }

        num_items getSize() { return (root == nullptr) ? 0 : root->size; }
        item_key getMin() { return (root == nullptr) ? std::numeric_limits<item_key>::max() : root->min; }
        item_key getMax() { return (root == nullptr) ? std::numeric_limits<item_key>::min() : root->max; }
        void updateProperties() {
            if (root != nullptr) {
                root->size = 1+root->left.getSize()+root->right.getSize();
                root->min = std::min(root->key, std::min(root->left.getMin(), root->right.getMin()));
                root->max = std::max(root->key, std::max(root->left.getMax(), root->right.getMax()));
            }
        }

        static treap<item_key, item_value> mergeTreaps(treap<item_key, item_value> left, treap<item_key, item_value> right) {
            if (left.root == nullptr) return right;
            if (right.root == nullptr) return left;
            if (left.root->priority > right.root->priority) {
                left.root->right = mergeTreaps(left.root->right, right);
                left.updateProperties();
                return left;
            } else {
                right.root->left = mergeTreaps(left, right.root->left);
                right.updateProperties();
                return right;
            }
        }

        //Split treap into a left-side with all elements less than or equal to key and a right-side with the rest of the elements.
        //Note that if exclusive is true, then left-side will have all elements less than key and right-side will have all elements greater than or equal to key.
        treap_pair<item_key, item_value> splitByKey(item_key key, bool exclusive) {
            treap_pair<item_key, item_value> answer;
            if (root == nullptr) return answer;

            //If the key is less than the key of the root, then all items less than or equal to key are on the left-hand side.
            if (exclusive ? (key <= root->key) : (key < root->key)) {
                answer = root->left.splitByKey(key, exclusive);
                //Since answer.left is the tree rooted at key, make answer.right, which has all elements greater than key but less than the key of the root, the new left node of the treap:
                root->left = answer.right;
                //After making this modification, this becomes the right-side, which has all elements greater than key:
                answer.right = *this;
            }
            //If the key is greater than or equal to the key of the root, then we know that the left-side and the root is composed of all elements less than or equal to key, so we need to search the right-hand side for any other elements which are less than or equal to key.
            else {
                answer = root->right.splitByKey(key, exclusive);
                //Now, we need to combine this treap and its left-side with all of the elements in the right-side which are also less than or equal to key.
                //These elements are now in answer.left, so make answer.left the new right-side of treap:
                root->right = answer.left;
                //After making this modification, this becomes the left-side, which has all elements less than or equal to key:
                answer.left = *this;
            }
            updateProperties();
            return answer;
        }

        item_value getKeyRangeSum(item_key startKey, item_key endKey) {
            //Split the treap up into a left-side which has all elements up to endKey:
            treap_pair<item_key, item_value> parts = splitByKey(endKey, false);
            //Split that treap up into a left-side which has all elements up to startKey-1:
            treap_pair<item_key, item_value> parts2 = parts.left.splitByKey(startKey, true);
            //Get the sum of the elements greater than startKey, less than or equal to endKey:
            item_value result = parts2.right.getSum();
            //Merge the treaps back together:
            root = mergeTreaps(mergeTreaps(parts2.left, parts2.right), parts.right).root;
            return result;
        }

        num_items countPointsInKeyRange(item_key startKey, item_key endKey) {
            //Split the treap up into a left-side which has all elements up to endKey:
            treap_pair<item_key, item_value> parts = splitByKey(endKey, false);
            //Split that treap up into a left-side which has all elements up to startKey-1:
            treap_pair<item_key, item_value> parts2 = parts.left.splitByKey(startKey, true);
            //Get the number of the elements greater than startKey, less than or equal to endKey:
            num_items result = parts2.right.getSize();
            //Merge the treaps back together:
            root = mergeTreaps(mergeTreaps(parts2.left, parts2.right), parts.right).root;
            return result;
        }

        bool addElementByKey(item_key newKey, item_value newValue, bool exclusive) {
            //Split treap up into a left-side with all elements less than newKey:
            treap_pair<item_key, item_value> parts = splitByKey(newKey, false);
            //Make sure newKey is not already in the tree:
            if (exclusive) {
                treap_pair<item_key, item_value> parts2 = parts.left.splitByKey(newKey, true);
                if (parts2.right.root != nullptr) {
                    root = mergeTreaps(mergeTreaps(parts2.left, parts2.right), parts.right).root;
                    return false;
                }
                parts.left = mergeTreaps(parts2.left, parts2.right);
            }

            //Create a new node:
            treap<item_key, item_value> storeTreap = newTreapNode<item_key, item_value>(newKey, newValue);
            //Put the new node to the right of the left-side, and then merge the new left-side with the right-side:
            root = mergeTreaps(mergeTreaps(parts.left, storeTreap), parts.right).root;

            return true;
        }

        bool removeElementByKey(item_key oldKey) {
            //Split treap up into a left-side which has all elements up to oldKey:
            treap_pair<item_key, item_value> parts = splitByKey(oldKey, false);
            //Now, split the left-side up into a left-side which has all elements before oldKey and a right-side which has all elements equal to oldKey:
            treap_pair<item_key, item_value> parts2 = parts.left.splitByKey(oldKey, true);
            //Record whether there were actually any elements with oldKey:
            bool actuallyRemoved = parts2.right.root != nullptr;
            //Merge treaps back together without the elements equal to oldKey:
            root = mergeTreaps(parts2.left, parts.right).root;

            return actuallyRemoved;
        }

        //Split treap into a left-side with the first pos elements and a right-side with the rest of the elements.
        //The left-side will be rooted with the (pos-1)th item (0-based indexing), if it exists.
        treap_pair<item_key, item_value> splitByPos(num_items pos) {
            treap_pair<item_key, item_value> answer;
            if (this->root == nullptr) return answer;
            if (pos > getSize()) {
                answer.left = *this;
                return answer;
            }

            num_items leftSize = root->left.getSize();
            //If the left-side has pos elements or more, then the (pos-1)th element is on the left-side:
            if (pos <= leftSize) {
                answer = root->left.splitByPos(pos);
                //Since answer.left is the tree rooted at (pos-1)th element, make answer.right, the elements between the (pos-1)th element and the root, the new left node of the treap:
                root->left = answer.right;
                //After making this modification, treap1 becomes the right-side, which has all elements after the (pos-1)th one:
                answer.right = *this;
            }
            //Otherwise, we need to split the right-side up to look for the (pos-1)th element:
            else {
                //Notice that we subtract pos by the number of elements in the root and left-side:
                answer = root->right.splitByPos(pos-leftSize-1);
                //Now, in order to get all of the first pos elements, we need to combine treap1 and its left-side with all of the elements in the right-side.
                //These elements are now in answer.left, so make answer.left the new right-side of treap:
                root->right = answer.left;
                //After making this modification, treap1 becomes the left-side, which has all of the first pos elements:
                answer.left = *this;
            }
            updateProperties();
            return answer;
        }

        item_value getIntervalSum(num_items startPos, num_items endPos) {
            //Split the treap up into a left-side which has all elements up to endPos index:
            treap_pair<item_key, item_value> parts = splitByPos(endPos+1);
            //Split that treap up into a left-side which has all elements up to startPos-1 index:
            treap_pair<item_key, item_value> parts2 = parts.left.splitByPos(startPos);
            //Get the sum of the elements with index greater than startPos-1, less than or equal to endPos:
            item_value result = parts2.right.getSum();
            //Merge the treaps back together:
            root = mergeTreaps(mergeTreaps(parts2.left, parts2.right), parts.right).root;
            return result;
        }

        void addElementByPos(num_items newPos, item_key newKey, item_value newValue) {
            //Split treap up into a left-side with first pos elements:
            treap_pair<item_key, item_value> parts = splitByPos(newPos);
            //Create the new node:
            treap<item_key, item_value> storeTreap = newTreapNode<item_key, item_value>(newKey, newValue);
            //Put the new node to the right of the left-side, and then merge the new left-side with the right-side:
            root = mergeTreaps(mergeTreaps(parts.left, storeTreap), parts.right).root;
        }

        bool removeElementByPos(num_items oldPos) {
            //If the index is too big or too small, we can't remove it:
            if (oldPos+1 > getSize()) return false;
            if (oldPos < 0) return false;

            //Split treap up into a left-side which has the first (oldPos+1) elements:
            treap_pair<item_key, item_value> parts = splitByPos(oldPos+1);
            //Now, separate out the first oldPos elements from this left-side in order to isolate the (oldPos)th element:
            treap_pair<item_key, item_value> parts2 = parts.left.splitByPos(oldPos);
            //Merge treaps back together without the isolated element:
            root = mergeTreaps(parts2.left, parts.right).root;

            return true;
        }

        treap getNodeAtPos(num_items pos) {
            //If the index is too big or too small, we can't find its value:
            if (pos < 0) return nullptr;
            if (pos > getSize()) return nullptr;

            treap<item_key, item_value> curTreap = *this;
            //Keep looking for the treap whose root is the (pos)th element:
            while (curTreap.root->left.getSize() != pos) {
                //If the left subtree has less than pos elements, then the (pos)th element must be in the right subtree.
                //Also, adjust pos accordingly.
                if (curTreap.root->left.getSize() < pos) {
                    pos -= curTreap.root->left.getSize()+1;
                    curTreap = curTreap.root->right;
                }
                //Otherwise, the (pos)th element must be in the left subtree.
                else curTreap = curTreap.root->left;

                if (curTreap.root == nullptr) puts("Treap size values are corrupted"), exit(1);
            }
            //Finally, return the treap that we just found:
            return curTreap;
        }
    };


    const num_items MAX_SPACE = 4000000;
    template <class item_key, class item_value> node<item_key, item_value> space[MAX_SPACE];
    template <class item_key, class item_value> num_items numSpaceUsed;
    template <class item_key, class item_value> treap<item_key, item_value> newTreapNode(item_key key, item_value value) {
        if (numSpaceUsed<item_key, item_value> >= MAX_SPACE) puts("Ran out of treap node space"), exit(1);

        space<item_key, item_value>[numSpaceUsed<item_key, item_value>].priority = rand();
        space<item_key, item_value>[numSpaceUsed<item_key, item_value>].key = key;
        space<item_key, item_value>[numSpaceUsed<item_key, item_value>].value = value;
        space<item_key, item_value>[numSpaceUsed<item_key, item_value>].left = treap<item_key, item_value>();
        space<item_key, item_value>[numSpaceUsed<item_key, item_value>].right = treap<item_key, item_value>();

        treap<item_key, item_value> newNode(space<item_key, item_value>+numSpaceUsed<item_key, item_value>);
        newNode.updateProperties();

        numSpaceUsed<item_key, item_value>++;
        return newNode;
    }

    //Used to initialize internal treap with empty items:
    template <class item_type> struct default_item {
        item_type operator*() { return item_type(); }
        default_item &operator+(int a) { return *this; }
    };
}

namespace range_tree {
    //Used with std::sort to sort a bunch of dim-dimensional points by a single coordinate.
    template<class item_type, ssize_t dimension, ssize_t coord> struct compare_by_coord {
        bool operator()(const std::array<item_type, dimension> &point1, const std::array<item_type, dimension> &point2) {
            return point1[coord] < point2[coord];
        }
    };

    //Used to pretend that an array of points is actually an array of coordinates.
    //Helpful for building treaps.
    template<class item_type, ssize_t dimension, ssize_t coord> struct mock_coordinate_array {
        std::array<item_type, dimension> *ptr;
        mock_coordinate_array(std::array<item_type, dimension> *p) : ptr(p) {}
        item_type operator*() { return (*ptr)[coord]; }
        mock_coordinate_array operator+(int offset) { return ptr+offset; }
    };

    //subtree<item_type, dim, lev> is a lev-dimensional range tree on a set of dim-dimensional vectors.
    //All range trees start as subtree<item_type, dim, dim>, which contains a bunch of subtree<item_type, dim, dim-1>, each of which contains a bunch of subtree<item_type, dim, dim-2>, etc. until we get down to subtree<item_type, dim, 2>
    template<class item_type, ssize_t dimension, ssize_t level> struct subtree {
        treap::treap<item_type, subtree<item_type, dimension, level-1>> internalTree;
    };

    //Alias so people can just use tree<item_type, dim> instead of subtree<item_type, dim, dim>
    template <class item_type, ssize_t dimension> using tree = subtree<item_type, dimension, dimension>;

    template<class item_type, ssize_t dimension> struct subtree<item_type, dimension, 2> {
        typedef std::array<item_type, dimension> point;
        typedef treap::treap<item_type, point> item_value;
        typedef treap::treap<item_type, item_value> internal_tree_type;
        internal_tree_type internalTree;

        static constexpr int MAX_SPACE = 2000000;
        static item_type itemStorageSpace[MAX_SPACE];
        static std::array<item_type, dimension> pointStorageSpace[MAX_SPACE];

        subtree(num_items numItems, point *points) {
            //Sort by the (dimension-2) coordinate:
            std::sort(points, points+numItems, compare_by_coord<item_type, dimension, dimension-2>());
            //Find how many unique (dimension-2) coordinates there are among the points:
            num_items numUniqueCoords = 0;
            for (num_items i = 0; i < numItems; i++) {
                if ((i == 0) || (points[i][dimension-2] != points[i-1][dimension-2])) itemStorageSpace[numUniqueCoords++] = points[i][dimension-2];
            }
            //Build the treap by using these unique coordinates as the keys:
            internalTree = internal_tree_type(numUniqueCoords, itemStorageSpace, treap::default_item<item_value>());

            //Sort by the (dimension-1) coordinate:
            std::sort(points, points+numItems, compare_by_coord<item_type, dimension, dimension-1>());
            //Build the 1D range trees:
            buildTreapAtNode(internalTree, numItems, points);
        }

        void buildTreapAtNode(internal_tree_type node, num_items numItems, point *points) {
            if (node.root == nullptr) return;

            //Build the 1D range tree at this node:
            node.root->value = item_value(numItems, mock_coordinate_array<item_type, dimension, dimension-1>(points), points);
            //Find the number of points that should go in the left and right subtrees, respectively, based off their (dimension-2) coordinate:
            num_items numLessThanRoot = 0, numGreaterThanRoot = 0;
            for (num_items i = 0; i < numItems; i++) {
                if (points[i][dimension-2] < node.root->key) pointStorageSpace[numLessThanRoot++] = points[i];
                if (points[i][dimension-2] < node.root->key) pointStorageSpace[numItems-(++numGreaterThanRoot)] = points[i];
            }
            //Copy the points over from storage space into the original array:
            memcpy(points, pointStorageSpace, numItems*sizeof(point));
            //Build the treaps at the children:

        }
    };

    template<class item_type, ssize_t dimension> item_type subtree<item_type, dimension, 2>::itemStorageSpace[subtree<item_type, dimension, 2>::MAX_SPACE];
}

typedef int32_t num;

template<class item_value> void print(treap::treap<num, item_value> tr) {
    if (tr.root == nullptr) return;
    print(tr.root->left);
    printf("%d %d %d %d %d\n", tr.root->key, tr.root->min, tr.root->max, tr.root->value[0], tr.root->value[1]);
    print(tr.root->right);
}

int main() {
    num_items NUM_ITEMS = 11;
    std::array<num, 2> points[NUM_ITEMS] = {{26, 1}, {98, 11}, {90, 8}, {68, 98}, {84, 67}, {13, 7}, {13, 9}, {43, 8}, {32, 77}, {6, 77}, {33, 47}};
    range_tree::tree<num, 2> test(NUM_ITEMS, points);
    print(test.internalTree.root->value);

    /* num_items NUM_ITEMS = 10;
    int32_t arr[NUM_ITEMS] = {1, 2, 3, 4, 6, 9, 10, 1203, 2000, 3000};
    int32_t arr2[NUM_ITEMS] = {1, 23, 31, -4, 5, 2, 56, 23, 1, 3};
    treap::treap<int32_t, int32_t> test(NUM_ITEMS, arr, default_item());
    for (int i = 0; i < test.getSize(); i++) {
        printf("%d\n", test.getNodeAtPos(i).root->value);
    } // */
    exit(0);
}