#include <iostream>
#include <vector>
#include <algorithm>
class Set {
private:
std::vector<int64_t> vector;
Set mergeSet(Set const first, Set const second) {
std::vector<int64_t> vector = {};
Set new_set(vector);
new_set.vector.insert(new_set.vector.end(),
first.vector.begin(),
first.vector.end());
new_set.vector.insert(new_set.vector.end(),
first.vector.begin(),
first.vector.end());
return new_set;
}
int64_t position(std::vector<int64_t> array,
int64_t number, int64_t left,
int64_t right
) {
int64_t mid = (left + right) / 2;
int64_t midNumber = array[mid];
if (number == midNumber) {
return -1;
}
if (left + 1 == right)
return mid ? mid + 1 : 0;
if (number > midNumber) {
return position(array, number, mid, right);
} else {
return position(array, number, left, mid);
}
}
int64_t searchRemove(std::vector<int64_t> array,
int64_t number,
int64_t left,
int64_t right) {
int64_t mid = (left + right) / 2;
int64_t numberMid = array[mid];
if (number == numberMid)
return mid;
if (left + 1 == right) {
return -1;
}
if (number > numberMid) {
return searchRemove(array, number, mid, right);
} else {
return searchRemove(array, number, left, mid);
}
}
static void deleteDuplicate(Set *set, std::vector<int64_t> array) {
set->vector.push_back(array[0]);
for (size_t i = 1; i < array.size(); i++) {
if (array[i] != set->vector[set->vector.size() - 1]) {
set->vector.push_back(array[i]);
}
}
};
public:
explicit Set(std::vector<int64_t> array) {
sort(array.begin(), array.end());
deleteDuplicate(this, array);
}
void Add(int64_t number) {
if (!this->vector.empty()) {
int64_t pos = position(this->vector,
number,
0,
this->vector.size());
if (pos != -1) {
this->vector.insert(vector.begin() + pos, number);
}
} else {
this->vector.push_back(number);
}
}
void Remove(int64_t number) {
int64_t pos = searchRemove(vector, number, 0, vector.size());
if (pos != -1) {
int64_t s = vector.size() - 1;
for (int64_t i = pos; i < s; i++) {
this->vector[i] = vector[i + 1];
}
this->vector.pop_back();
}
}
bool Contains(int64_t number) {
if (position(vector,
number,
0,
vector.size()) == -1) {
return true;
} else {
return false;
}
}
std::vector<int64_t> Data() {
return this->vector;
}
Set &operator=(const Set &other) {
this->vector.clear();
this->vector.insert(this->vector.end(),
other.vector.begin(),
other.vector.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->vector.end(),
other.begin(),
other.end());
return *p;
}
Set Union(const Set &second) {
Set tmp_s(this->vector);
int64_t s_tmp = tmp_s.vector.size() - 1;
int64_t s_s = second.vector.size() - 1;
if (tmp_s.vector[0] > second.vector[s_s]) {
return mergeSet(second, tmp_s);
} else if ((tmp_s.vector[s_tmp] < second.vector[0])) {
return mergeSet(tmp_s, second);
} else {
for (int64_t i = 0; i < s_s + 1; i++) {
tmp_s.Add(second.vector[i]);
}
}
return tmp_s;
}
Set Intersection(const Set &second) {
std::vector<int64_t> vector = {};
Set new_set(vector);
int64_t s_s = second.vector.size() - 1;
int64_t s = this->vector.size();
if (this->vector[0] > second.vector[s_s] ||
(this->vector[s - 1] < second.vector[0])) {
return new_set;
} else {
for (auto x : this->vector) {
if (std::find(second.vector.begin(),
second.vector.end(), x) != second.vector.end()) {
new_set.Add(x);
}
}
return new_set;
}
}
Set Difference(const Set &second) {
std::vector<int64_t> vector = {};
Set new_set(vector);
int64_t s_s = second.vector.size() - 1;
if (this->vector[0] > second.vector[s_s] ||
(this->vector[this->vector.size() - 1] < second.vector[0])) {
return *this;
} else {
for (int64_t i : this->vector) {
if (searchRemove(second.vector, i,
0, second.vector.size()) == -1) {
new_set.Add(i);
}
}
}
return new_set;
}
Set SymmetricDifference(const Set &second) {
std::vector<int64_t> vector = {};
Set new_set(vector);
for (auto x : this->vector) {
if (std::find(second.vector.begin(),
second.vector.end(), x) == second.vector.end()) {
new_set.Add(x);
}
}
for (auto x : second.vector) {
if (std::find(this->vector.begin(),
this->vector.end(), x) == this->vector.end()) {
new_set.Add(x);
}
}
return new_set;
}
};