#include <iostream>
#include <vector>
#include <algorithm>
class Set {
private:
std::vector<int64_t> vec;
Set MergeSet(Set const second, Set const first) {
Set tmp;
tmp.vec.insert(tmp.vec.end(), second.vec.begin(), second.vec.end());
tmp.vec.insert(tmp.vec.end(), first.vec.begin(), first.vec.end());
return tmp;
}
int64_t BinSearchPosition(std::vector<int64_t> v,
int64_t digit, int64_t left,
int64_t right
) {
int64_t mid = (left + right) / 2;
int64_t Digit_mid = v[mid];
if (digit == Digit_mid) {
return -1;
}
if (left + 1 == right)
return mid ? mid + 1 : 0;
if (digit > Digit_mid) {
return BinSearchPosition(v, digit, mid, right);
} else {
return BinSearchPosition(v, digit, left, mid);
}
}
int64_t BinSearch_Remove(std::vector<int64_t> v,
int64_t digit,
int64_t left,
int64_t right) {
int64_t mid = (left + right) / 2;
int64_t Digit_mid = v[mid];
if (digit == Digit_mid)
return mid;
if (left + 1 == right) {
return -1;
}
if (digit > Digit_mid) {
return BinSearch_Remove(v, digit, mid, right);
} else {
return BinSearch_Remove(v, digit, left, mid);
}
}
public:
explicit Set(std::vector<int64_t> v) {
sort(v.begin(), v.end());
this->vec.push_back(v[0]);
for (size_t i = 1; i < v.size(); i++) {
if (v[i] != this->vec[this->vec.size() - 1]) {
this->vec.push_back(v[i]);
}
}
}
Set() {
}
void Add(int64_t digit) {
int64_t pos = BinSearchPosition(this->vec, digit, 0, vec.size());
if (pos != -1) {
this->vec.insert(vec.begin() + pos, digit);
}
}
void Remove(int64_t digit) {
int64_t pos = BinSearch_Remove(vec, digit, 0, vec.size());
if (pos != -1) {
int64_t s = vec.size() - 1;
for (int64_t i = pos; i < s; i++) {
this->vec[i] = vec[i + 1];
}
this->vec.pop_back();
}
}
bool Contains(int64_t digit) {
if (BinSearchPosition(vec, digit, 0, vec.size()) == -1) {
return true;
} else {
return false;
}
}
std::vector<int64_t> Data() {
return this->vec;
}
Set &operator=(const Set &other) {
this->vec.clear();
this->vec.insert(this->vec.end(), other.vec.begin(), other.vec.end());
return *this;
}
std::vector<int64_t> &operator=(const std::vector<int64_t> &other) {
std::vector<int64_t> v;
std::vector<int64_t> *p = &v;
v.insert(this->vec.end(), other.begin(), other.end());
return *p;
}
Set Union(const Set &second) {
Set tmp_s(this->vec);
int64_t s_tmp = tmp_s.vec.size() - 1;
int64_t s_s = second.vec.size() - 1;
if (tmp_s.vec[0] > second.vec[s_s]) {
return MergeSet(second, tmp_s);
} else if ((tmp_s.vec[s_tmp] < second.vec[0])) {
return MergeSet(tmp_s, second);
} else {
for (int64_t i = 0; i < second.vec.size(); i++) {
tmp_s.Add(second.vec[i]);
}
}
return tmp_s;
}
Set Intersection(const Set &second) {
Set TMP;
int64_t s_s = second.vec.size() - 1;
if (this->vec[0] > second.vec[s_s] ||
(this->vec[this->vec.size() - 1] < second.vec[0])) {
return TMP;
} else {
for (int64_t i = 0; i < this->vec.size(); i++) {
if (BinSearch_Remove(
second.vec,
this->vec[i],
0,
second.vec.size()) != -1) {
TMP.Add(this->vec[i]);
}
}
}
return TMP;
}
Set Difference(const Set &second) {
Set TMP;
int64_t s_s = second.vec.size() - 1;
if (this->vec[0] > second.vec[s_s] ||
(this->vec[this->vec.size() - 1] < second.vec[0])) {
return TMP;
} else {
for (int64_t i : this->vec) {
if (BinSearch_Remove(second.vec,
i,
0,
second.vec.size()) == -1) {
TMP.Add(i);
}
}
}
return TMP;
}
Set SymmetricDifference(const Set &second) {
int64_t s_s = second.vec.size() - 1;
if (this->vec[0] > second.vec[s_s] ||
(this->vec[this->vec.size() - 1] < second.vec[0])) {
return MergeSet(*this, second);
} else {
std::vector<int64_t> tmp_vec(this->vec);
tmp_vec.insert(tmp_vec.end(), second.vec.begin(), second.vec.end());
return Set(tmp_vec);
}
}
};