#pragma once
#include <vector>
#include <cstdint>
class Set {
public:
Set(const std::vector<int64_t>& a = {});
Set Union(const Set&) const;
Set Difference(const Set&) const;
Set SymmetricDifference(const Set&) const;
Set Intersection(const Set&) const;
void Add(int64_t);
void Remove(int64_t);
bool Contains(int64_t) const;
std::vector<int64_t> Data() const;
std::vector<int64_t> c;
};
const int n = 1000007;
void Set::Add(int64_t val) {
int i = (val * 3 + 11) % c.size();
while (c[i] != -1 && c[i] != val) {
i = (i + 17) % c.size();
}
c[i] = val;
}
void Set::Remove(int64_t val) {
int i = (val * 3 + 11) % c.size();
while (c[i] != -1 && c[i] != val) {
i = (i + 17) % c.size();
}
if (c[i] == val) {
c[i] = -2;
}
}
bool Set::Contains(int64_t val) const {
int i = (val * 3 + 11) % c.size();
while (c[i] != -1 && c[i] != val) {
i = (i + 17) % c.size();
}
return (c[i] == val);
}
Set::Set(const std::vector<int64_t>& a) {
c.assign(n, -1);
for (int i = 0; i < a.size(); i++)
Add(a[i]);
}
Set Set::Union(const Set& b) const {
Set new_set;
for (int i = 0; i < n; i++) {
if (c[i] >= 0)
new_set.Add(c[i]);
if (b.c[i] >= 0)
new_set.Add(b.c[i]);
}
return new_set;
}
Set Set::Intersection(const Set& b) const {
Set new_set;
for (int i = 0; i < n; i++) {
if (c[i] >= 0 && b.Contains(c[i]))
new_set.Add(c[i]);
}
return new_set;
}
Set Set::Difference(const Set& b) const {
Set new_set;
for (int i = 0; i < n; i++) {
if (c[i] >= 0 && !(b.Contains(c[i])))
new_set.Add(c[i]);
}
return new_set;
}
Set Set::SymmetricDifference(const Set& b) const {
Set new_set;
for (int i = 0; i < n; i++) {
if (c[i] >= 0 && !(b.Contains(c[i])))
new_set.Add(c[i]);
if (b.c[i] >= 0 && !(Contains(b.c[i])))
new_set.Add(b.c[i]);
}
return new_set;
}
std::vector<int64_t> Set::Data() const {
std::vector<int64_t> ans;
for (int i = 0; i < n; i++) {
if (c[i] >= 0)
ans.push_back(c[i]);
}
return ans;
}