#include <limits>
#include <vector>
#include <tuple>
#include <iostream>

using namespace std;

// If the condition is not true, report an error and halt.
#define EXPECT(condition, message) do { if (!(condition)) expect_failed(message); } while (0)

void expect_failed(const string& message);

/*** One node ***/

class ab_node {
  public:
    // Keys stored in this node and the corresponding children
    // The vectors are large enough to accommodate one extra entry
    // in overflowing nodes.
    vector<ab_node *> children;
    vector<int> keys;
    ab_node *parent;

    // If this node contains the given key, return true and set i to key's position.
    // Otherwise return false and set i to the first key greater than the given one.
    bool find_branch(int key, int &i)
    {
        i = 0;
        while (i < keys.size() && keys[i] <= key) {
            if (keys[i] == key)
                return true;
            i++;
        }
        return false;
    }

    // Insert a new key at position i and add a new child between keys i and i+1.
    void insert_branch(int i, int key, ab_node *child)
    {
        keys.insert(keys.begin() + i, key);
        children.insert(children.begin() + i + 1, child);
    }

    // An auxiliary function for displaying a sub-tree under this node.
    void show(int indent);
};

/*** Tree ***/

class ab_tree {
  public:
    int a;          // Minimum allowed number of children
    int b;          // Maximum allowed number of children
    ab_node *root;  // Root node (even a tree with no keys has a root)
    int num_nodes;  // We keep track of how many nodes the tree has

    // Create a new node and return a pointer to it.
    ab_node *new_node(ab_node* parent)
    {
        ab_node *n = new ab_node;
        n->keys.reserve(b);
        n->children.reserve(b+1);
        n->parent = parent;
        num_nodes++;
        return n;
    }

    // Delete a given node, assuming that its children have been already unlinked.
    void delete_node(ab_node *n)
    {
        num_nodes--;
        delete n;
    }

    // Constructor: initialize an empty tree with just the root.
    ab_tree(int a, int b)
    {
        EXPECT(a >= 2 && b >= 2*a - 1, "Invalid values of a,b");
        this->a = a;
        this->b = b;
        num_nodes = 0;
        // The root has no keys and one null child pointer.
        root = new_node(nullptr);
        root->children.push_back(nullptr);
    }

    // An auxiliary function for deleting a subtree recursively.
    void delete_tree(ab_node *n)
    {
        for (int i=0; i < n->children.size(); i++)
            if (n->children[i])
                delete_tree(n->children[i]);
        delete_node(n);
    }

    // Destructor: delete all nodes.
    ~ab_tree()
    {
        delete_tree(root);
        EXPECT(num_nodes == 0, "Memory leak detected: some nodes were not deleted");
    }

    // Find a key: returns true if it is present in the tree.
    bool find(int key)
    {
        ab_node *n = root;
        while (n) {
            int i;
            if (n->find_branch(key, i))
                return true;
            n = n->children[i];
        }
        return false;
    }

    // Delete the smallest element.
    void delete_min() {
        ab_node *node = root;
        while (node->children[0])
            node = node->children[0];

        node->children.erase(node->children.begin());
        node->keys.erase(node->keys.begin());

        while (node->children.size() < a && node->parent) {
            node = node->parent;
            ab_node *first = node->children[0], *second = node->children[1];

            // Merge the second to the first
            if (second->children.size() == a) {
                for (auto &c : second->children) {
                    first->children.push_back(c);
                    if (c)
                        c->parent = first;
                }
                node->children.erase(node->children.begin()+1);

                first->keys.push_back(node->keys[0]);
                node->keys.erase(node->keys.begin());
                for (auto &k : second->keys)
                    first->keys.push_back(k);

                delete_node(second);
            }

            // Move the leftest child of the second to the first
            else {
                second->children[0]->parent = first;
                first->children.push_back(second->children[0]);
                second->children.erase(second->children.begin());

                first->keys.push_back(node->keys[0]);
                node->keys[0] = second->keys[0];
                second->keys.erase(second->keys.begin());
            }
        }

        if (node->children.size() == 1) {
            node->children[0]->parent = nullptr;
            root = node->children[0];
            delete_node(node);
        }
    }

    // Display the tree on standard output in human-readable form.
    void show();

    // Check that the data structure satisfies all invariants.
    void audit();

    // Split the node into two nodes: move some children of n into 
    // a newly created node such that n contains exactly size children in the end.
    // Return the new node and the key separating n and the new node.
    virtual pair<ab_node*, int> split_node(ab_node* n, int size)
    {
        // FIXME: Implement
    }

    // Insert: add key to the tree (unless it was already present).
    virtual void insert(int key)
    {
        // FIXME: Implement
    }
};