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

typedef int64_t num_items;

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

    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;
        bst<item_key, item_value> left;
        bst<item_key, item_value> right;
    };

    template <class item_key, class item_value> bst<item_key, item_value> newBstNode(item_key key, item_value value);

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

        template <class item_key_container, class item_value_container> bst(num_items numItems, item_key_container keyArr, item_value_container valueArr) {
            //Return an empty bst if there are no items:
            if (numItems == 0) {
                root = nullptr;
                return;
            }

            //Find where the median is located:
            num_items medianPos = numItems/2;
            //Create a new node out of the median:
            root = newBstNode(keyArr[medianPos], valueArr[medianPos]).root;
            //Build the left and right sides accordingly:
            root->left = bst<item_key, item_value>(medianPos, keyArr, valueArr);
            root->right = bst<item_key, item_value>(numItems-medianPos-1, keyArr+medianPos+1, valueArr+medianPos+1);
            //Given the new child nodes, update the bst's properties:
            updateProperties();
        }

        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; }
#ifdef USE_SUM
        item_value getSum() { return (root == nullptr) ? 0 : root->sum; }
#endif
        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()));
#ifdef USE_SUM
                root->sum = root->value+root->left.getSum()+root->right.getSum();
#endif
            }
        }

        num_items countItemsInKeyRange(item_key start, item_key end) {
            if (root == nullptr) return 0;
            //printf("%ld %ld %ld | %ld %ld\n", root->min, root->max, root->size, start, end);
            if (start > root->max) return 0;
            if (end < root->min) return 0;
            if ((start <= root->min) && (end >= root->max)) return root->size;

            bool rootInInterval = (start <= root->key) && (end >= root->key);
            return rootInInterval+root->left.countItemsInKeyRange(start, end)+root->right.countItemsInKeyRange(start, end);
        }
    };

#ifdef USE_STATIC
    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 = 0;
    template <class item_key, class item_value> bst<item_key, item_value> newBstNode(item_key key, item_value value) {
        if (numSpaceUsed<item_key, item_value> >= MAX_SPACE) puts("Ran out of bst 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 = bst<item_key, item_value>();
        space<item_key, item_value>[numSpaceUsed<item_key, item_value>].right = bst<item_key, item_value>();

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

        numSpaceUsed<item_key, item_value>++;
        return newNode;
    }
#else
    template <class item_key, class item_value> bst<item_key, item_value> newBstNode(item_key key, item_value value) {
        bst<item_key, item_value> newNode(new node<item_key, item_value>());
        newNode.root->priority = rand();
        newNode.root->key = key;
        newNode.root->value = value;
        newNode.root->left = bst<item_key, item_value>();
        newNode.root->right = bst<item_key, item_value>();
        newNode.updateProperties();
        return newNode;
    }
#endif

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

namespace range_tree {
    //Used with std::sort to sort a bunch of dim-dimensional points by a single coordinate.
    template<class item_type, size_t dimension, size_t coord> struct compare_by_coord {
        static bool lessThan(const std::array<item_type, dimension> &point1, const std::array<item_type, dimension> &point2) {
             for (size_t i = 0; i < dimension; i++) {
                 size_t indexToBeExamined = (coord+i) % dimension;
                 if (point1[indexToBeExamined] != point2[indexToBeExamined]) return point1[indexToBeExamined] < point2[indexToBeExamined];
             }
             return false;
        }

        static bool greaterThan(const std::array<item_type, dimension> &point1, const std::array<item_type, dimension> &point2) {
             for (size_t i = 0; i < dimension; i++) {
                 size_t indexToBeExamined = (coord+i) % dimension;
                 if (point1[indexToBeExamined] != point2[indexToBeExamined]) return point1[indexToBeExamined] > point2[indexToBeExamined];
             }
             return false;
        }

        bool operator()(const std::array<item_type, dimension> &point1, const std::array<item_type, dimension> &point2) { return lessThan(point1, point2); }
    };

    //Used to pretend that an array of points is actually an array of coordinates.
    //Helpful for building bsts.
    template<class item_type, size_t dimension, size_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; }
        item_type operator[](int offset) { return ptr[offset][coord]; }
    };

    //Used to pretend that an array of points is actually an array of points paired with an empty bst.
    //Helpful for building bsts.
    template<class point, class bst> struct mock_pair_array {
        point *ptr;
        mock_pair_array(point *p) : ptr(p) {}
        std::pair<point, bst> operator*() { return std::pair<point, bst>(*ptr, bst()); }
        mock_pair_array operator+(int offset) { return ptr+offset; }
        std::pair<point, bst> operator[](int offset) { return std::pair<point, bst>(ptr[offset], bst()); }
    };

    //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, size_t dimension, size_t level> struct subtree {
        bst::bst<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, size_t dimension> using tree = subtree<item_type, dimension, dimension>;

    template<class item_type, size_t dimension> struct subtree<item_type, dimension, 2> {
        typedef std::array<item_type, dimension> point;
        typedef bst::bst<item_type, point> lesser_tree;
        typedef std::pair<point, lesser_tree> item_value;
        typedef bst::bst<item_type, item_value> internal_tree_type;
        internal_tree_type internalTree;

        static constexpr int MAX_SPACE = 2000000;
        static point 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>());
            //Build the bst by using these unique coordinates as the keys:
            internalTree = internal_tree_type(numItems, mock_coordinate_array<item_type, dimension, dimension-2>(points), mock_pair_array<point, lesser_tree>(points));

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

        void buildBstAtNode(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.second = lesser_tree(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:
            //Make sure to preserve the relative order of the elements so we can easily build the 1D range trees in the children nodes.
            num_items numLessThanRoot = 0, numGreaterThanRoot = 0;
            for (size_t i = 0; i < numItems; i++) {
                if (compare_by_coord<item_type, dimension, dimension-2>::lessThan(points[i], node.root->value.first)) pointStorageSpace[numLessThanRoot++] = points[i];
            }
            for (size_t i = 0; i < numItems; i++) {
                if (compare_by_coord<item_type, dimension, dimension-2>::greaterThan(points[i], node.root->value.first)) pointStorageSpace[numLessThanRoot+(numGreaterThanRoot++)] = points[i];
            }
            //Copy the points over from storage space into the original array:
            memcpy(points, pointStorageSpace, (numLessThanRoot+numGreaterThanRoot)*sizeof(point));
            //Build the bsts at the children:
            buildBstAtNode(node.root->left, numLessThanRoot, points);
            buildBstAtNode(node.root->right, numGreaterThanRoot, points+numLessThanRoot);
        }

        num_items countPointsInRange(point minPoint, point maxPoint) {
            countPointsInRangeAtNode(internalTree, minPoint, maxPoint);
        }

        num_items countPointsInRangeAtNode(internal_tree_type node, point minPoint, point maxPoint) {
            if (node.root == nullptr) return 0;

            //Get the start and end coordinates for both the (dimension-2) and (dimension-1) coordinates:
            item_type startCoord = minPoint[dimension-2], startCoord2 = minPoint[dimension-1];
            item_type endCoord = maxPoint[dimension-2], endCoord2 = maxPoint[dimension-1];
            //If the query interval is out of range of this node, return 0:
            if (startCoord > node.getMax()) return 0;
            if (endCoord < node.getMin()) return 0;
            //If the node's interval is entirely within the query interval, delegate the query to the 1D range tree:
            if ((startCoord <= node.getMin()) && (endCoord >= node.getMax())) return node.root->value.second.countItemsInKeyRange(startCoord2, endCoord2);

            //Calculate whether or not the root point is within the query interval.
            bool rootInInterval = true;
            for (size_t i = 0; i < dimension; i++) if ((minPoint[i] > node.root->value.first[i]) || (maxPoint[i] < node.root->value.first[i])) {
                rootInInterval = false;
                break;
            }
            //Finally, keep recursing the query to both of the children:
            return rootInInterval+countPointsInRangeAtNode(node.root->left, minPoint, maxPoint)+countPointsInRangeAtNode(node.root->right, minPoint, maxPoint);
        }
    };

    template<class item_type, size_t dimension> std::array<item_type, dimension> subtree<item_type, dimension, 2>::pointStorageSpace[subtree<item_type, dimension, 2>::MAX_SPACE];
}

typedef int32_t num;

template<class item_value> void print(bst::bst<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);
}

template<class item_value> void printSpecial(bst::bst<num, item_value> tr) {
    if (tr.root == nullptr) return;
    printSpecial(tr.root->left);
    printf("%d %d %d\n", tr.root->key, tr.root->min, tr.root->max);
    puts("---------------------------");
    print(tr.root->value.second);
    puts("---------------------------");
    printSpecial(tr.root->right);
}

//#define BULK_TEST

#ifdef BULK_TEST
const num_items NUM_ITEMS = 1000000;
std::array<num, 2> points[NUM_ITEMS];
#else
const 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}};
#endif

int main() {
#ifdef BULK_TEST
    for (num_items i = 0; i < NUM_ITEMS; i++) {
        points[i][0] = rand();
        points[i][1] = rand();
    }
#endif
    range_tree::tree<num, 2> test(NUM_ITEMS, points);
    //print(test.internalTree.root->value.second);
    printf("%ld\n", test.internalTree.root->value.second.countItemsInKeyRange(10, 70));
    printf("%ld\n", test.countPointsInRange(std::array<num, 2>{10, 0}, std::array<num, 2>{70, 70}));
    //printSpecial(test.internalTree); // */

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