#include <bits/stdc++.h>
using namespace std;

// ==================== Node ====================

template <typename Type, int Ord>
struct Node
{
    bool is_leaf;
    int num_keys;
    Type key[Ord];

    Node(bool leaf)
    {
        is_leaf = leaf;
        num_keys = 0;
    }

    virtual ~Node() = default;
};

// ==================== Leaf Node ====================

template <typename Type, int Ord>
struct LeafNode : public Node<Type, Ord>
{
    LeafNode() : Node<Type, Ord>(true) {}
};

// ==================== Internal Node ====================

template <typename Type, int Ord>
struct InternalNode : public Node<Type, Ord>
{
    Node<Type, Ord>* child[Ord + 1];

    InternalNode() : Node<Type, Ord>(false)
    {
        for (int i = 0; i <= Ord; i++)
            child[i] = nullptr;
    }
};

// ==================== B Tree ====================

template <typename Type, int Ord>
struct BTree
{
private:
    static_assert(Ord >= 3, "Ord must be at least 3");

    Node<Type, Ord>* root = nullptr;

    static constexpr int MIN_KEYS = (Ord + 1) / 2 - 1;

    // ==================== Search ====================

    bool searchNode(Node<Type, Ord>* node, Type value) const
    {
        if (node == nullptr)
            return false;

        int i;

        for (i = 0; i < node->num_keys; i++)
        {
            if (value <= node->key[i]) break;
        }

        if (i < node->num_keys && value == node->key[i])
            return true;

        if (node->is_leaf)
            return false;

        auto* p = static_cast<InternalNode<Type, Ord>*>(node);

        return searchNode(p->child[i], value);
    }

    // ==================== Split Leaf ====================

    bool splitLeaf(Node<Type, Ord>* node, Type value,
                   Type& promoted, Node<Type, Ord>*& right)
    {
        Type temp[Ord + 1];

        int i;

        for (i = node->num_keys - 1; i >= 0; i--)
        {
            if (value >= node->key[i]) break;
            temp[i + 1] = node->key[i];
        }

        temp[i + 1] = value;

        for (int j = 0; j <= i; j++)
            temp[j] = node->key[j];

        int mid = (Ord + 1) / 2;

        promoted = temp[mid];

        right = new LeafNode<Type, Ord>();

        node->num_keys = mid;

        for (int j = 0; j < mid; j++)
            node->key[j] = temp[j];

        right->num_keys = Ord - mid;

        for (int j = 0; j < right->num_keys; j++)
            right->key[j] = temp[mid + 1 + j];

        return true;
    }

    // ==================== Split Internal ====================

    bool splitInternal(Node<Type, Ord>* node, int pos,
                       Type value, Node<Type, Ord>* newChild,
                       Type& promoted, Node<Type, Ord>*& right)
    {
        auto* p = static_cast<InternalNode<Type, Ord>*>(node);

        Type tempKeys[Ord + 1];
        Node<Type, Ord>* tempChildren[Ord + 2];

        for (int i = 0; i < pos; i++)
            tempKeys[i] = node->key[i];

        tempKeys[pos] = value;

        for (int i = pos; i < node->num_keys; i++)
            tempKeys[i + 1] = node->key[i];

        for (int i = 0; i <= pos; i++)
            tempChildren[i] = p->child[i];

        tempChildren[pos + 1] = newChild;

        for (int i = pos + 1; i <= node->num_keys; i++)
            tempChildren[i + 1] = p->child[i];

        int mid = (Ord + 1) / 2;

        promoted = tempKeys[mid];

        right = new InternalNode<Type, Ord>();

        auto* r = static_cast<InternalNode<Type, Ord>*>(right);

        node->num_keys = mid;

        for (int i = 0; i < mid; i++)
            node->key[i] = tempKeys[i];

        for (int i = 0; i <= mid; i++)
            p->child[i] = tempChildren[i];

        for (int i = mid + 1; i <= Ord; i++)
            p->child[i] = nullptr;

        right->num_keys = Ord - mid;

        for (int i = 0; i < right->num_keys; i++)
            right->key[i] = tempKeys[mid + 1 + i];

        for (int i = 0; i <= right->num_keys; i++)
            r->child[i] = tempChildren[mid + 1 + i];

        return true;
    }

    // ==================== Insert ====================

    bool insertRecursive(Node<Type, Ord>* node, Type value,
                         Type& promoted, Node<Type, Ord>*& right)
    {
        if (node->is_leaf)
        {
            if (node->num_keys < Ord)
            {
                int i;

                for (i = node->num_keys - 1; i >= 0; i--)
                {
                    if (value >= node->key[i]) break;
                    node->key[i + 1] = node->key[i];
                }

                node->key[i + 1] = value;
                node->num_keys++;

                return false;
            }

            return splitLeaf(node, value, promoted, right);
        }

        auto* p = static_cast<InternalNode<Type, Ord>*>(node);

        int pos;

        for (pos = 0; pos < node->num_keys; pos++)
        {
            if (value <= node->key[pos]) break;
        }

        Type childPromoted{};
        Node<Type, Ord>* childRight = nullptr;

        if (!insertRecursive(p->child[pos], value,
                             childPromoted, childRight))
            return false;

        if (node->num_keys < Ord)
        {
            for (int i = node->num_keys; i > pos; i--)
                node->key[i] = node->key[i - 1];

            for (int i = node->num_keys + 1; i > pos + 1; i--)
                p->child[i] = p->child[i - 1];

            node->key[pos] = childPromoted;
            p->child[pos + 1] = childRight;
            node->num_keys++;

            return false;
        }

        return splitInternal(node, pos, childPromoted, childRight,
                             promoted, right);
    }

    // ==================== Get Predecessor ====================

    Type getPredecessor(Node<Type, Ord>* node) const
    {
        while (!node->is_leaf)
        {
            auto* p = static_cast<InternalNode<Type, Ord>*>(node);
            node = p->child[node->num_keys];
        }

        return node->key[node->num_keys - 1];
    }

    // ==================== Remove From Leaf ====================

    void removeFromLeaf(Node<Type, Ord>* node, int idx)
    {
        for (int i = idx; i < node->num_keys - 1; i++)
            node->key[i] = node->key[i + 1];

        node->num_keys--;
    }

    // ==================== Borrow From Previous ====================

    void borrowFromPrev(Node<Type, Ord>* parent, int idx)
    {
        auto* p = static_cast<InternalNode<Type, Ord>*>(parent);

        Node<Type, Ord>* child = p->child[idx];
        Node<Type, Ord>* sibling = p->child[idx - 1];

        for (int i = child->num_keys; i > 0; i--)
            child->key[i] = child->key[i - 1];

        if (!child->is_leaf)
        {
            auto* c = static_cast<InternalNode<Type, Ord>*>(child);
            auto* s = static_cast<InternalNode<Type, Ord>*>(sibling);

            for (int i = child->num_keys + 1; i > 0; i--)
                c->child[i] = c->child[i - 1];

            c->child[0] = s->child[sibling->num_keys];
            s->child[sibling->num_keys] = nullptr;
        }

        child->key[0] = parent->key[idx - 1];

        parent->key[idx - 1] = sibling->key[sibling->num_keys - 1];

        child->num_keys++;
        sibling->num_keys--;
    }

    // ==================== Borrow From Next ====================

    void borrowFromNext(Node<Type, Ord>* parent, int idx)
    {
        auto* p = static_cast<InternalNode<Type, Ord>*>(parent);

        Node<Type, Ord>* child = p->child[idx];
        Node<Type, Ord>* sibling = p->child[idx + 1];

        child->key[child->num_keys] = parent->key[idx];

        if (!child->is_leaf)
        {
            auto* c = static_cast<InternalNode<Type, Ord>*>(child);
            auto* s = static_cast<InternalNode<Type, Ord>*>(sibling);

            c->child[child->num_keys + 1] = s->child[0];

            for (int i = 0; i < sibling->num_keys; i++)
                s->child[i] = s->child[i + 1];

            s->child[sibling->num_keys] = nullptr;
        }

        parent->key[idx] = sibling->key[0];

        for (int i = 0; i < sibling->num_keys - 1; i++)
            sibling->key[i] = sibling->key[i + 1];

        child->num_keys++;
        sibling->num_keys--;
    }

    // ==================== Merge ====================

    void merge(Node<Type, Ord>* parent, int idx)
    {
        auto* p = static_cast<InternalNode<Type, Ord>*>(parent);

        Node<Type, Ord>* left = p->child[idx];
        Node<Type, Ord>* right = p->child[idx + 1];

        int size = left->num_keys;

        left->key[size] = parent->key[idx];

        for (int i = 0; i < right->num_keys; i++)
            left->key[size + 1 + i] = right->key[i];

        if (!left->is_leaf)
        {
            auto* l = static_cast<InternalNode<Type, Ord>*>(left);
            auto* r = static_cast<InternalNode<Type, Ord>*>(right);

            for (int i = 0; i <= right->num_keys; i++)
            {
                l->child[size + 1 + i] = r->child[i];
                r->child[i] = nullptr;
            }
        }

        left->num_keys += right->num_keys + 1;

        for (int i = idx; i < parent->num_keys - 1; i++)
            parent->key[i] = parent->key[i + 1];

        for (int i = idx + 1; i < parent->num_keys; i++)
            p->child[i] = p->child[i + 1];

        p->child[parent->num_keys] = nullptr;

        parent->num_keys--;

        delete right;
    }

    // ==================== Fix Underflow ====================

    void fixChild(Node<Type, Ord>* parent, int idx)
    {
        auto* p = static_cast<InternalNode<Type, Ord>*>(parent);

        Node<Type, Ord>* child = p->child[idx];

        if (child->num_keys >= MIN_KEYS)
            return;

        if (idx > 0 && p->child[idx - 1]->num_keys > MIN_KEYS)
            borrowFromPrev(parent, idx);
        else if (idx < parent->num_keys &&
                 p->child[idx + 1]->num_keys > MIN_KEYS)
            borrowFromNext(parent, idx);
        else if (idx < parent->num_keys)
            merge(parent, idx);
        else if (idx > 0)
            merge(parent, idx - 1);
    }

    // ==================== Remove ====================

    bool removeRecursive(Node<Type, Ord>* node, Type value)
    {
        int idx;

        for (idx = 0; idx < node->num_keys; idx++)
        {
            if (value <= node->key[idx]) break;
        }

        if (idx < node->num_keys && value == node->key[idx])
        {
            if (node->is_leaf)
            {
                removeFromLeaf(node, idx);
                return true;
            }

            auto* p = static_cast<InternalNode<Type, Ord>*>(node);

            Type pred = getPredecessor(p->child[idx]);

            node->key[idx] = pred;

            bool removed = removeRecursive(p->child[idx], pred);

            if (removed)
                fixChild(node, idx);

            return removed;
        }

        if (node->is_leaf)
            return false;

        auto* p = static_cast<InternalNode<Type, Ord>*>(node);

        bool removed = removeRecursive(p->child[idx], value);

        if (removed)
            fixChild(node, idx);

        return removed;
    }

    // ==================== Display ====================

    void displayNode(Node<Type, Ord>* node, int level) const
    {
        if (node == nullptr)
            return;

        cout << string(level * 4, ' ') << "[ ";

        for (int i = 0; i < node->num_keys; i++)
            cout << node->key[i] << " ";

        cout << "]\n";

        if (!node->is_leaf)
        {
            auto* p = static_cast<InternalNode<Type, Ord>*>(node);

            for (int i = 0; i <= node->num_keys; i++)
                displayNode(p->child[i], level + 1);
        }
    }

    // ==================== Destroy ====================

    void destroy(Node<Type, Ord>* node)
    {
        if (node == nullptr)
            return;

        if (!node->is_leaf)
        {
            auto* p = static_cast<InternalNode<Type, Ord>*>(node);

            for (int i = 0; i <= node->num_keys; i++)
                destroy(p->child[i]);
        }

        delete node;
    }

public:

    BTree() = default;

    ~BTree()
    {
        destroy(root);
    }

    BTree(const BTree&) = delete;
    BTree& operator=(const BTree&) = delete;

    // ==================== Search ====================

    bool search(Type value) const
    {
        return searchNode(root, value);
    }

    // ==================== Insert ====================

    void insert(Type value)
    {
        if (search(value))
        {
            cout << "Value already exists!\n";
            return;
        }

        if (root == nullptr)
        {
            root = new LeafNode<Type, Ord>();
            root->key[0] = value;
            root->num_keys = 1;

            return;
        }

        Type promoted{};
        Node<Type, Ord>* right = nullptr;

        if (insertRecursive(root, value, promoted, right))
        {
            auto* newRoot = new InternalNode<Type, Ord>();

            newRoot->key[0] = promoted;
            newRoot->num_keys = 1;

            newRoot->child[0] = root;
            newRoot->child[1] = right;

            root = newRoot;
        }
    }

    // ==================== Remove ====================

    void remove(Type value)
    {
        if (root == nullptr)
        {
            cout << "Tree is empty!\n";
            return;
        }

        if (!search(value))
        {
            cout << "Value not found!\n";
            return;
        }

        removeRecursive(root, value);

        if (root->num_keys == 0)
        {
            Node<Type, Ord>* oldRoot = root;

            if (root->is_leaf)
            {
                root = nullptr;
            }
            else
            {
                auto* p = static_cast<InternalNode<Type, Ord>*>(root);

                root = p->child[0];
                p->child[0] = nullptr;
            }

            delete oldRoot;
        }
    }

    // ==================== Display ====================

    void displayTree() const
    {
        if (root == nullptr)
        {
            cout << "Tree is empty!\n";
            return;
        }

        displayNode(root, 0);
    }
};

// ==================== Main ====================

int main()
{
    BTree<int, 3> tree;

    int choice;
    int value;

    while (true)
    {
        cout << "\n========== B-Tree ==========\n";
        cout << "1. Insert\n";
        cout << "2. Delete\n";
        cout << "3. Search\n";
        cout << "4. Display\n";
        cout << "0. Exit\n";

        cout << "Choice: ";
        cin >> choice;

        switch (choice)
        {
            case 1:
                cout << "Enter value: ";
                cin >> value;
                tree.insert(value);
                break;

            case 2:
                cout << "Enter value: ";
                cin >> value;
                tree.remove(value);
                break;

            case 3:
                cout << "Enter value: ";
                cin >> value;

                if (tree.search(value))
                    cout << "Found!\n";
                else
                    cout << "Not Found!\n";

                break;

            case 4:
                tree.displayTree();
                break;

            case 0:
                cout << "Goodbye!\n";
                break;

            default:
                cout << "Invalid choice!\n";
        }

        if (choice == 0) break;
    }

    return 0;
}