#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define isz(x) (int)(x).size()
typedef unsigned long long ull;
const uint64_t seed = (uint64_t)(std::chrono::high_resolution_clock::now().time_since_epoch().count());
const int mod = int((1LL << 31) - 1);
int remainder(uint64_t x) {
    x = (x >> 31) + (x & mod) + 1;
    x = (x >> 31) + (x & mod);
    return int((x >> 31) + (x & mod) - 1);
}
 
struct CustomHash {
    uint64_t operator()(uint64_t x) const {
        static const uint64_t a = remainder(seed);
        static const uint64_t b = remainder(a * a);
        static const uint64_t c = remainder(a * b);
        static const uint64_t d = remainder(a * c);
        static const uint64_t m = (1 << 16) - 1;
        return remainder((x&m)*a+((x>>16)&m)*b+((x>>32)&m)*c+((x>>48)&m)*d);
    }
};
 
template<typename HashType>
void report(const char * filename) {
// This function reads numbers from file `filename` and counts number of collisios
    std::map<int,int> collisions;
    auto file = fopen(filename, "rt");
    for (ull num; fscanf(file, "%llu", &num) == 1; ) {
        auto res = HashType()(num);
        collisions[res & ((1 << 18) - 1)]++;
    }
    fclose(file);
    std::vector<int> vec;
    for (auto p : collisions) { vec.push_back(p.second-1); }
    std::sort(all(vec));
    auto median = vec[isz(vec)/2];
    auto average = std::accumulate(all(vec), 1.0) / isz(vec);
    std::cerr << "report for file " << filename << ":\n";
    std::cerr << "buckets = " << collisions.size() << "\n";
    std::cerr << "average collisions num = " << average << "\n";
    std::cerr << "median of collisions num = " << median << "\n";
    std::cerr << "max = " << vec.back() << "\n";
    std::cerr << "min = " << vec.front() << "\n";
}
 
int main() {
	std::cout << std::fixed << std::setprecision(3);
    //report<CustomHash>("stat1.txt");
    // This part of code test CustomHash on runtime:
    double tin = (double)clock();
    std::mt19937 gen(seed);
    std::uniform_int_distribution<uint64_t> dist(ull(0), ~ull(0));
    ull sum = 0;
    const int numOper = 50 * 1000 * 1000;
    for (int i = 0; i < numOper; i++) {
        sum += CustomHash()(dist(gen));        
    }
    double tout = ((double)clock() - tin) / CLOCKS_PER_SEC;
    std::cout << "checksum = " << sum << std::endl;
    std::cout << "number of operations is " << numOper << ", runtime is " << tout << "s" << std::endl;
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgYWxsKHgpICh4KS5iZWdpbigpLCh4KS5lbmQoKQojZGVmaW5lIGlzeih4KSAoaW50KSh4KS5zaXplKCkKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgdWxsOwpjb25zdCB1aW50NjRfdCBzZWVkID0gKHVpbnQ2NF90KShzdGQ6OmNocm9ubzo6aGlnaF9yZXNvbHV0aW9uX2Nsb2NrOjpub3coKS50aW1lX3NpbmNlX2Vwb2NoKCkuY291bnQoKSk7CmNvbnN0IGludCBtb2QgPSBpbnQoKDFMTCA8PCAzMSkgLSAxKTsKaW50IHJlbWFpbmRlcih1aW50NjRfdCB4KSB7CiAgICB4ID0gKHggPj4gMzEpICsgKHggJiBtb2QpICsgMTsKICAgIHggPSAoeCA+PiAzMSkgKyAoeCAmIG1vZCk7CiAgICByZXR1cm4gaW50KCh4ID4+IDMxKSArICh4ICYgbW9kKSAtIDEpOwp9CgpzdHJ1Y3QgQ3VzdG9tSGFzaCB7CiAgICB1aW50NjRfdCBvcGVyYXRvcigpKHVpbnQ2NF90IHgpIGNvbnN0IHsKICAgICAgICBzdGF0aWMgY29uc3QgdWludDY0X3QgYSA9IHJlbWFpbmRlcihzZWVkKTsKICAgICAgICBzdGF0aWMgY29uc3QgdWludDY0X3QgYiA9IHJlbWFpbmRlcihhICogYSk7CiAgICAgICAgc3RhdGljIGNvbnN0IHVpbnQ2NF90IGMgPSByZW1haW5kZXIoYSAqIGIpOwogICAgICAgIHN0YXRpYyBjb25zdCB1aW50NjRfdCBkID0gcmVtYWluZGVyKGEgKiBjKTsKICAgICAgICBzdGF0aWMgY29uc3QgdWludDY0X3QgbSA9ICgxIDw8IDE2KSAtIDE7CiAgICAgICAgcmV0dXJuIHJlbWFpbmRlcigoeCZtKSphKygoeD4+MTYpJm0pKmIrKCh4Pj4zMikmbSkqYysoKHg+PjQ4KSZtKSpkKTsKICAgIH0KfTsKCnRlbXBsYXRlPHR5cGVuYW1lIEhhc2hUeXBlPgp2b2lkIHJlcG9ydChjb25zdCBjaGFyICogZmlsZW5hbWUpIHsKLy8gVGhpcyBmdW5jdGlvbiByZWFkcyBudW1iZXJzIGZyb20gZmlsZSBgZmlsZW5hbWVgIGFuZCBjb3VudHMgbnVtYmVyIG9mIGNvbGxpc2lvcwogICAgc3RkOjptYXA8aW50LGludD4gY29sbGlzaW9uczsKICAgIGF1dG8gZmlsZSA9IGZvcGVuKGZpbGVuYW1lLCAicnQiKTsKICAgIGZvciAodWxsIG51bTsgZnNjYW5mKGZpbGUsICIlbGx1IiwgJm51bSkgPT0gMTsgKSB7CiAgICAgICAgYXV0byByZXMgPSBIYXNoVHlwZSgpKG51bSk7CiAgICAgICAgY29sbGlzaW9uc1tyZXMgJiAoKDEgPDwgMTgpIC0gMSldKys7CiAgICB9CiAgICBmY2xvc2UoZmlsZSk7CiAgICBzdGQ6OnZlY3RvcjxpbnQ+IHZlYzsKICAgIGZvciAoYXV0byBwIDogY29sbGlzaW9ucykgeyB2ZWMucHVzaF9iYWNrKHAuc2Vjb25kLTEpOyB9CiAgICBzdGQ6OnNvcnQoYWxsKHZlYykpOwogICAgYXV0byBtZWRpYW4gPSB2ZWNbaXN6KHZlYykvMl07CiAgICBhdXRvIGF2ZXJhZ2UgPSBzdGQ6OmFjY3VtdWxhdGUoYWxsKHZlYyksIDEuMCkgLyBpc3oodmVjKTsKICAgIHN0ZDo6Y2VyciA8PCAicmVwb3J0IGZvciBmaWxlICIgPDwgZmlsZW5hbWUgPDwgIjpcbiI7CiAgICBzdGQ6OmNlcnIgPDwgImJ1Y2tldHMgPSAiIDw8IGNvbGxpc2lvbnMuc2l6ZSgpIDw8ICJcbiI7CiAgICBzdGQ6OmNlcnIgPDwgImF2ZXJhZ2UgY29sbGlzaW9ucyBudW0gPSAiIDw8IGF2ZXJhZ2UgPDwgIlxuIjsKICAgIHN0ZDo6Y2VyciA8PCAibWVkaWFuIG9mIGNvbGxpc2lvbnMgbnVtID0gIiA8PCBtZWRpYW4gPDwgIlxuIjsKICAgIHN0ZDo6Y2VyciA8PCAibWF4ID0gIiA8PCB2ZWMuYmFjaygpIDw8ICJcbiI7CiAgICBzdGQ6OmNlcnIgPDwgIm1pbiA9ICIgPDwgdmVjLmZyb250KCkgPDwgIlxuIjsKfQoKaW50IG1haW4oKSB7CglzdGQ6OmNvdXQgPDwgc3RkOjpmaXhlZCA8PCBzdGQ6OnNldHByZWNpc2lvbigzKTsKICAgIC8vcmVwb3J0PEN1c3RvbUhhc2g+KCJzdGF0MS50eHQiKTsKICAgIC8vIFRoaXMgcGFydCBvZiBjb2RlIHRlc3QgQ3VzdG9tSGFzaCBvbiBydW50aW1lOgogICAgZG91YmxlIHRpbiA9IChkb3VibGUpY2xvY2soKTsKICAgIHN0ZDo6bXQxOTkzNyBnZW4oc2VlZCk7CiAgICBzdGQ6OnVuaWZvcm1faW50X2Rpc3RyaWJ1dGlvbjx1aW50NjRfdD4gZGlzdCh1bGwoMCksIH51bGwoMCkpOwogICAgdWxsIHN1bSA9IDA7CiAgICBjb25zdCBpbnQgbnVtT3BlciA9IDUwICogMTAwMCAqIDEwMDA7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG51bU9wZXI7IGkrKykgewogICAgICAgIHN1bSArPSBDdXN0b21IYXNoKCkoZGlzdChnZW4pKTsgICAgICAgIAogICAgfQogICAgZG91YmxlIHRvdXQgPSAoKGRvdWJsZSljbG9jaygpIC0gdGluKSAvIENMT0NLU19QRVJfU0VDOwogICAgc3RkOjpjb3V0IDw8ICJjaGVja3N1bSA9ICIgPDwgc3VtIDw8IHN0ZDo6ZW5kbDsKICAgIHN0ZDo6Y291dCA8PCAibnVtYmVyIG9mIG9wZXJhdGlvbnMgaXMgIiA8PCBudW1PcGVyIDw8ICIsIHJ1bnRpbWUgaXMgIiA8PCB0b3V0IDw8ICJzIiA8PCBzdGQ6OmVuZGw7CiAgICByZXR1cm4gMDsKfQ==