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

class HashTable {
private:
    
    const int P = 127;
    const float LOAD_FACTOR_LIMIT = 0.75;
    
    vector<list<pair<string, int>>> table;
    int numberOfBuckets, numberOfElements;

    int Add(int a, int b) {
        return (a + b) % numberOfBuckets; 
    }

    int mul(int a, int b) {
        return 1ll * a * b % numberOfBuckets;
    }

    int Hash(string s) {
        int pow = 1;
        int h = 0;
        for (int i = 0; s[i]; i++) {
            h = Add(h, mul(s[i], pow));
            pow = mul(pow, P);
        }
        return h;
    }

    void rehash() {
        numberOfBuckets *= 2;
        vector<list<pair<string, int>>> newTable(numberOfBuckets);
        for (auto lst : table) {
            for (auto x : lst) {
                int bucketNumber = Hash(x.first);
                newTable[bucketNumber].push_back({x.first, x.second});
            }
        }
        table = newTable;
    }

    void update(string key, int val) {
        int bucketNumber = Hash(key);
        auto &lst = table[bucketNumber];
        for (auto it = lst.begin(); it != lst.end(); it++) {
            if ((*it).first == key) {
                (*it).second = val;
                return;
            }
        }
    }

public:
    HashTable() {
        numberOfBuckets = 8;
        table.resize(numberOfBuckets);
        numberOfElements = 0;
    }

    void insert(string key, int value) {
        if (get(key)) {
            update(key, value);
            return;
        }
        float currentLoadFactor = 1.0 * numberOfElements / numberOfBuckets;
        if (currentLoadFactor >= LOAD_FACTOR_LIMIT) rehash();
        int bucketNumber = Hash(key);
        table[bucketNumber].push_back({key, value});
        numberOfElements++;
    }

    int get(string key) {
        int bucketNumber = Hash(key);
        auto &lst = table[bucketNumber];
        for (auto it = lst.begin(); it != lst.end(); it++) {
            if ((*it).first == key) return (*it).second;
        }
        return 0;
    }

    void addOne(string key) {
        insert(key, get(key) + 1);
    }

    void remove(string key) {
        int bucketNumber = Hash(key);
        auto &lst = table[bucketNumber];
        for (auto it = lst.begin(); it != lst.end(); it++) {
            if ((*it).first == key) {
                lst.erase(it);
                numberOfElements--;
                return;
            }
        }
    }

    int size() {
        return numberOfElements;
    }

    bool empty() {
        return numberOfElements == 0;
    }

    void print() {
        for (int i = 0; i < numberOfBuckets; i++) {
            cout << i << ":\t";
            for (auto x : table[i]) {
                cout << '(' << x.first << ", " << x.second << ") -> ";
            }
            cout << "NULL\n";
        }
        cout << "\t===============================================\n\n";
    }
};

int main()
{

    return 0;
}