void push(const std::string& k, T val)
{
    Node* e(new Node);
    e->key = k; e->value = val;
    e->left = e->right = nullptr;
    if (root) push(root, e);
    else root = e;
}

void push(Node*& s, Node*& e)
{
    if (s) {
        if (s->key < e->key) push(s->right, e);
        else push(s->left, e);
    }
    else s = e;
}

void push(Node*& s, Node* e)
{
    Node** head = &s;
    while (*head != nullptr) {
        head = ((*head)->key < e->key) ? &(*head)->right : &(*head)->left;
    }
    *head = e;
}

void push(const std::string& k, T val)
{
    Node* e(new Node);
    e->key = k; e->value = val;
    e->left = e->right = nullptr;
    if (root) push(root, k) = e;
    else root = e;
}
Node*& push(Node*& s, const std::string& k)
{
    if (s) {
        if (s->key < k) push(s->right, k);
        else push(s->left, k);
    }
    else return s;
}