//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx")

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <cassert>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <tuple>
#include <array>
#include <string_view>
#include <list>
#include <future>
#include <mutex>

#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define hm unordered_map
#define pii pair<int, int>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define cinv(v) for (auto& x: v) cin >> x
#define fr(i, n) for (int i = 0; i < (n); ++i)
#define fl(i, l, n) for (int i = (l); i < (n); ++i)

// #define int ll

template<typename T1, typename T2>
inline bool chkmin(T1 &x, const T2 &y) {
    if (x > y) {
        x = y;
        return 1;
    }
    return 0;
}

template<typename T1, typename T2>
inline bool chkmax(T1 &x, const T2 &y) {
    if (x < y) {
        x = y;
        return 1;
    }
    return 0;
}

using namespace std;

#ifdef LOCAL
#define dbg(x) cerr << #x << " : " << x << endl
#else
#define dbg(x)
#endif

//tg: @runningcherry

template<typename Collection>
string Join(const Collection &col) {
    bool first = true;
    stringstream ss;
    for (const auto &x: col) {
        if (!first) ss << ", ";
        first = false;
        ss << x;
    }
    return ss.str();
}

template<typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &v) {
    return out << '{' << v.fi << ", " << v.se << '}';
}

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
    return out << '[' << Join(v) << ']';
}

template<typename T1, typename T2>
ostream &operator<<(ostream &out, const map<T1, T2> &v) {
    return out << '{' << Join(v) << '}';
}

template<typename T>
ostream &operator<<(ostream &out, const set<T> &v) {
    return out << '(' << Join(v) << ')';
}

template<typename T>
ostream &operator<<(ostream &out, const multiset<T> &v) {
    return out << '(' << Join(v) << ')';
}

template<typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &a) {
    return in >> a.fi >> a.se;
}

const ll inf = (ll) 2e9;

const int maxn = 1e5 + 20;

#define ASSERT_EQUAL(a, b) dbg((bool)(a == b))
#define ASSERT(a) dbg((bool)(a))

template <typename K, typename V>
class ConcurrentMap {
public:
    static_assert(is_integral_v<K>, "ConcurrentMap supports only integer keys");

    struct Access {
        lock_guard<mutex> g;
        V& ref_to_value;
    };

    explicit ConcurrentMap(size_t bucket_count) : mod (bucket_count) {
        kek = vector<Synchronized<map <K, V>>> (mod);
    }

    template <typename T>
    class Synchronized {
    public:
        explicit Synchronized(T initial = T()) : value(move(initial)) {}
        struct Access1 {
            T& ref_to_value;
            mutex& mm;
        };
        Access1 GetAccess() {
            return {value, m};
        }
    private:
        T value;
        mutex m;
    };

    Access operator[](const K& key) {
        int x = abs (key % mod);
        auto ptt = kek[x].GetAccess ();
        return {lock_guard (ptt.mm), ptt.ref_to_value[key]};
    }

    map<K, V> BuildOrdinaryMap() {
        map <K, V> res;
        fr (i, mod) {
            auto ptt = kek[i].GetAccess ();
            lock_guard g (ptt.mm);
            for (auto& x: ptt.ref_to_value) res[x.fi] = x.se;
        }
        return res;
    }

private:
    vector<Synchronized<map <K, V>>> kek;
    const int mod;
};

//int main () {
//    ios_base::sync_with_stdio (0);
//    cin.tie (0);
//
//
//}