#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define vll vector #define vvvl vector #define vvl vector> #define VV(a, b, c, d) vector>(a, vector(b, c)) #define VVV(a, b, c, d) vector(a, vvl(b, vll (c, d))); #define re(c, b) for(ll c=0;c struct hashset{ float load_factor = 0.8; int table_size = 16; int mod = 15; Key null_key; vector table; vector data; function f = std::hash(); hashset(): null_key(std::numeric_limits::max()), table(table_size, null_key){} int size(){ return data.size(); } void expand_table(){ table_size *= 2; mod = table_size - 1; table.resize(table_size); fill(table.begin(), table.end(), null_key); for(auto v:data) insert(v, false); } void insert(Key k, bool g=true){ assert(k!=null_key); uint32_t h = f(k) & mod; while(true){ if(table[h]!=null_key){ if(table[h]==k) return; h = (h + 1) & mod; }else{ if(g) data.push_back(k); table[h] = k; if(float(data.size())>load_factor*float(table_size)){ expand_table(); } return; } } } bool contain(Key k){ unsigned h = f(k) & mod; while(true){ if(table[h]==null_key) return false; if(table[h]==k) return true; h = (h + 1) & mod; } } }; template struct hashmap{ float load_factor = 0.8; int table_size = 16; int mod = 15; Key null_key; vector key_table; vector val_table; vector> data; function f = std::hash(); hashmap(): null_key(std::numeric_limits::max()), key_table(table_size, null_key), val_table(table_size){} int size(){ return data.size(); } void expand_table(){ table_size *= 2; mod = table_size - 1; key_table.resize(table_size); val_table.resize(table_size); fill(key_table.begin(), key_table.end(), null_key); for(auto d:data) emplace(d.first, d.second, false); } void emplace(Key k, Val v, bool g=true){ assert(k!=null_key); uint32_t h = f(k) & mod; while(true){ if(key_table[h]!=null_key){ if(key_table[h]==k) return; h = (h + 1) & mod; }else{ if(g) data.push_back({k, v}); key_table[h] = k; val_table[h] = v; if(float(data.size())>load_factor*float(table_size)){ expand_table(); } return; } } } bool contain(Key k){ assert(k!=null_key); unsigned h = f(k) & mod; while(true){ if(key_table[h]==null_key) return false; if(key_table[h]==k) return true; h = (h + 1) & mod; } } Val at(Key k){ assert(k!=null_key); unsigned h = f(k) & mod; while(true){ assert(key_table[h]!=null_key); if(key_table[h]==k) return val_table[h]; h = (h + 1) & mod; } } Val &at_ref(Key k){ assert(k!=null_key); unsigned h = f(k) & mod; while(true){ assert(key_table[h]!=null_key); if(key_table[h]==k) return val_table[h]; h = (h + 1) & mod; } } }; template struct hashmultiset{ private: float load_factor = 0.8; int table_size = 16; int mod = 15; Key null_key; vector key_table; vector idx_table; vector> data; function f = std::hash(); void expand_table(){ table_size *= 2; mod = table_size - 1; key_table.resize(table_size); idx_table.resize(table_size); fill(key_table.begin(), key_table.end(), null_key); for(int i=0;iload_factor*float(table_size)){ expand_table(); } return; } } } public: hashmultiset(): null_key(std::numeric_limits::max()), key_table(table_size, null_key), idx_table(table_size){} int size(){ return data.size(); } void insert(Key k){ assert(k!=null_key); uint32_t h = f(k) & mod; while(true){ if(key_table[h]!=null_key){ if(key_table[h]==k){ data[idx_table[h]].second++; return; } h = (h + 1) & mod; }else{ int idx = data.size(); data.push_back({k, 1}); key_table[h] = k; idx_table[h] = idx; if(float(data.size())>load_factor*float(table_size)){ expand_table(); } return; } } } int count(Key k){ assert(k!=null_key); unsigned h = f(k) & mod; while(true){ if(key_table[h]==null_key) return 0; if(key_table[h]==k) return data[idx_table[h]].second; h = (h + 1) & mod; } } }; int main(){ ll n, m;scanf("%lld %lld", &n, &m); //hashmultiset st; //map mp; for(int i=0;i