#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;
}