#include <iostream>

using namespace std;

template <typename T>
class Vector {

public:
    Vector() : size_(0), capacity_(4), arr_(new T[4]) {}

    explicit Vector(const int vector_capacity) : size_(0), capacity_(vector_capacity), arr_(new T[vector_capacity]) {}

    Vector(const Vector& other) : size_(other.size_), capacity_(other.capacity_), arr_(new T[capacity_]) {
        for (int i = 0; i < size_; i++) {
            arr_[i] = other.arr_[i];
        }
        total_number_elements_ += size_;
    } // конструктор копирования

    Vector(const initializer_list<T>& list) : size_(list.size()), capacity_(list.size()), arr_(new T[list.size()]) {
        int i = 0;
        for (const T& element : list) {
            arr_[i] = element;
            i++;
        }
    }

    Vector& operator=(const Vector& other) {
        if (&other != this) { // проверка на самоприсваивание
            total_number_elements_ += other.size_ - size_; // общее количество увеличивается (уменьшается) на разность элементов
            size_ = other.size_;
            capacity_ = other.capacity_;
            delete[] arr_;
            arr_ = new T[capacity_];
            for (int i = 0; i < size_; i++) {
                arr_[i] = other.arr_[i];
            }
        }
        return *this;
    } // копирующий оператор присваивания =

    Vector(Vector&& other) : size_(other.size_), capacity_(other.capacity_), arr_(other.arr_) {
        other.arr_ = nullptr;
        other.size_ = 0;
        other.capacity_ = 0;
    } // конструктор перемещения

    Vector& operator=(Vector&& other) {
        if (&other != this) {
            total_number_elements_ += other.size_ - size_; // общее количество увеличивается (уменьшается) на разность элементов
            size_ = other.size_;
            capacity_ = other.capacity_;
            delete[] arr_;
            arr_ = other.arr_;
            other.arr_ = nullptr;
            other.size_ = 0;
            other.capacity_ = 0;
        }
        return *this;
    } // перемещающий оператор присваивания =

    void push_back(const T& value) {
        check_capacity();
        arr_[size_] = value;
        size_++;
        total_number_elements_++;
    }

    void pop_back() {
        if (size_ > 0) {
            size_--;
        }
        total_number_elements_--;
    }

    void insert(const int index, const T& value) {
        if (index < 0 || index > size_) {
            cout << "Некорректный индекс" << endl;
            return;
        }
        check_capacity();
        for (int i = size_; i > index; i--) {
            arr_[i] = arr_[i - 1];
        }
        arr_[index] = value;
        size_++;
        total_number_elements_++;
    }

    void erase(const int index) {
        if (index < 0 || index >= size_) {
            cout << "Некорректный индекс" << endl;
            return;
        }
        for (int i = index; i < size_ - 1; i++) {
            arr_[i] = arr_[i + 1];
        }
        size_--;
        total_number_elements_--;
    }

    T& operator[](const int index) {
        if (index < 0 || index >= size_) {
            cout << "Некорректный индекс" << endl;
        }
        return arr_[index];
    }

    const T& operator[](const int index) const {
        if (index < 0 || index >= size_) {
            cout << "Некорректный индекс" << endl;
        }
        return arr_[index];
    }

    int size() const {
        return size_;
    }

    int capacity() const {
        return capacity_;
    }

    bool operator==(const Vector& right) const {
        if (right.size_ != size_) {
            return false;
        }
        for (int i = 0; i < size_; i++) {
            if (arr_[i] != right.arr_[i])
                return false;
        }
        return true;
    }

    bool operator!=(const Vector& right) const {
        return !(*this == right);
    }

    void print() const {
        for (int i = 0; i < size_; i++) {
            cout << arr_[i] << " ";
        }
        cout << endl;
    }

    static int get_total_number_elements() {
        return total_number_elements_;
    }


    ~Vector() {
        delete[] arr_;
        total_number_elements_ -= size_;
    }

private:

    void check_capacity() {
        if (size_ == capacity_) {
            int* temp = new int[capacity_ * 2];
            for (int i = 0; i < size_; i++) {
                temp[i] = arr_[i];
            }
            delete[] arr_;
            arr_ = temp;
            capacity_ *= 2;
        }
    }

    int size_; // текущее количество элементов
    int capacity_; // емкость хранилища
    T* arr_; // хранилище
    static int total_number_elements_; // общее количество элементов по всем векторам
};

template <typename T>
int Vector<T>::total_number_elements_ = 0;

template <typename T>
class List {
public:

    List() : size_(0), head_(nullptr), last_(nullptr) {}

    List(const List& other) : size_(0), head_(nullptr), last_(nullptr) {
        Node* temp = other.last_;
        while (temp != nullptr) {
            push_front(temp->value);
            temp = temp->prev;
        }
    }

    List(List&& other) : size_(other.size_), head_(other.head_), last_(other.last_) {
        other.head_ = other.last_ = nullptr;
    }

    List& operator=(const List& other) {
        if (this != &other) {
            clear();
            Node* temp = other.last_;
            while (temp != nullptr) {
                push_front(temp->value);
                temp = temp->prev;
            }
        }
        return *this;
    }

    List& operator=(List&& other) {
        if (this != &other) {
            clear();
            size_ = other.size_;
            head_ = other.head_;
            last_ = other.last_;
            other.head_ = other.last_ = nullptr;
        }
        return *this;
    }

    void push_front(const T& value) {
        if (size_ == 0) {
            last_ = head_ = new Node{ value, nullptr, nullptr };
            size_++;
            return;
        }
        Node* temp = new Node{ value, head_, nullptr };
        head_->prev = temp;
        head_ = temp;
        size_++;
    }

    void push_back(const T& value) {
        if (size_ == 0) {
            last_ = head_ = new Node{ value, nullptr, nullptr };
            size_++;
            return;
        }
        Node* temp = new Node{ value, nullptr, last_ };
        last_->next = temp;
        last_ = temp;
        size_++;
    }

    void pop_front() {
        if (size_ > 0) {
            if (size_ == 1) {
                delete head_;
                last_ = head_ = nullptr;
                size_--;
                return;
            }
            Node* temp = head_;
            head_ = head_->next;
            delete temp;
            head_->prev = nullptr;
            size_--;
        }
    }

    void pop_back() {
        if (size_ > 0) {
            if (size_ == 1) {
                delete head_;
                last_ = head_ = nullptr;
                size_--;
                return;
            }
            Node* temp = last_;
            last_ = last_->prev;
            delete temp;
            last_->next = nullptr;
            size_--;
        }
    }

    void insert(const int index, const T& value) {
        if (index == 0) {
            push_front(value);
            return;
        }
        if (index == size_) {
            push_back(value);
            return;
        }
        if (index > 0 && index < size_) {
            Node* temp = head_;
            for (int i = 0; i < index - 1; i++) {
                temp = temp->next;
            }
            Node* buf = new Node{ value, temp->next, temp };
            temp->next->prev = buf;
            temp->next = buf;
            size_++;
        }
    }

    void erase(const int index) {
        if (index == 0) {
            pop_front();
            return;
        }
        if (index == size_ - 1) {
            pop_back();
            return;
        }
        if (index > 0 && index < size_ - 1) {
            Node* temp = head_;
            for (int i = 0; i < index - 1; i++) {
                temp = temp->next;
            }
            Node* buf = temp->next->next;
            delete temp->next;
            temp->next = buf;
            buf->prev = temp;
            size_--;
        }
    }

    T& operator[] (const int index) {
        if (index >= 0 && index < size_) {
            Node* temp = head_;
            for (int i = 0; i < index; i++) {
                temp = temp->next;
            }
            return temp->value;
        }
    }

    const T& operator[] (const int index) const {
        if (index >= 0 && index < size_) {
            Node* temp = head_;
            for (int i = 0; i < index; i++) {
                temp = temp->next;
            }
            return temp->value;
        }
    }

    bool operator==(const List& other) const {
        if (size_ != other.size_) {
            return false;
        }
        Node* temp = head_;
        Node* other_temp = other.head_;

        while (temp != nullptr) {
            if (temp->value != other_temp->value) {
                return false;
            }
            temp = temp->next;
            other_temp = other_temp->next;
        }
        return true;
    }

    bool operator!=(const List& other) const {
        return !(*this == other);
    }

    int find(const T& value) const {
        int index = 0;
        Node* temp = head_;

        while (temp != nullptr && temp->value != value) {
            temp = temp->next;
            index++;
        }
        if (temp != nullptr) {
            return index;
        }
        return -1;
    }

    T& front() {
        if (head_ != nullptr) {
            return head_->value;
        }
    }

    const T& front() const {
        if (head_ != nullptr) {
            return head_->value;
        }
    }

    T& back() {
        if (last_ != nullptr) {
            return last_->value;
        }
    }

    const T& back() const {
        if (last_ != nullptr) {
            return last_->value;
        }
    }

    void print() {
        Node* temp = head_;
        while (temp != nullptr) {
            cout << temp->value << " ";
            temp = temp->next;
        }
        cout << endl;
    }

    int size() const {
        return size_;
    }

    void clear() {
        while (head_ != nullptr) {
            pop_front();
        }
    }

    ~List() {
        clear();
    }

private:
    struct Node { // двусвязный список состоит из узлов
        T value; // узел хранит информативную часть
        Node* next; // указатель на следующий узел в списке
        Node* prev; // указатель на предыдущий узел
    };

    int size_;
    Node* head_;
    Node* last_;
};

template<typename T>
class Set {

public:

    struct Node {
        T value;
        Node* left;
        Node* right;
        Node* parent;
    };

    Set() : root_(nullptr), size_(0) {}

    Set(const initializer_list<T>& list) : root_(nullptr), size_(0) {
        for (const T& element : list) {
            insert(element);
        }
    }

    Set(const Set& other) : root_(copy(other.root_, nullptr)), size_(other.size_) {}

    Set(Set&& other) : root_(other.root_), size_(other.size_) {
        other.root_ = nullptr;
    }

    Set& operator=(const Set& other) {
        if (this != &other) {
            clear();
            size_ = other.size_;
            root_ = copy(other.root_, nullptr);
        }
        return *this;
    }

    Set& operator=(Set&& other) {
        if (this != &other) {
            clear();
            size_ = other.size_;
            root_ = other.root_;
            other.root_ = nullptr;
        }
        return *this;
    }

    void insert(const T& val) {
        if (root_ == nullptr) {
            root_ = new Node{ val, nullptr, nullptr, nullptr };
            size_++;
            return;
        }
        Node* parent = nullptr;
        Node* node = root_;
        while (node != nullptr && node->value != val) {
            parent = node;
            node = node->value > val ? node->left : node->right;
        }
        if (node == nullptr) {
            node = new Node{ val, nullptr, nullptr, parent };
            parent->value > val ? parent->left = node : parent->right = node;
            size_++;
        }
    }

    void erase(const T& val) {
        Node* parent = nullptr;
        Node* node = root_;
        while (node != nullptr && node->value != val) {
            parent = node;
            node = node->value > val ? node->left : node->right;
        }
        if (node != nullptr) {
            if (node->left == nullptr && node->right == nullptr) {
                if (node == root_) {
                    root_ = nullptr;
                }
                else {
                    node == parent->right ? parent->right = nullptr : parent->left = nullptr;
                }
                delete node;
            }
            else if (node->left == nullptr) {
                node->right->parent = node->parent;
                if (node == root_) {
                    root_ = node->right;
                }
                else {
                    node == parent->right ? parent->right = node->right : parent->left = node->right;
                }
                delete node;
            }
            else if (node->right == nullptr) {
                node->left->parent = node->parent;
                if (node == root_) {
                    root_ = node->left;
                }
                else {
                    node == parent->right ? parent->right = node->left : parent->left = node->left;
                }
                delete node;
            }
            else {
                Node* temp = min(node->right);
                node->value = temp->value;
                if (temp->right != nullptr) {
                    temp->right->parent = temp->parent;
                }
                temp == temp->parent->right ? temp->parent->right = temp->right : temp->parent->left = temp->right;
                delete temp;
            }
            size_--;
        }
    }

    Node* min(Node* node) {
        if (node != nullptr) {
            while (node->left != nullptr) {
                node = node->left;
            }
        }
        return node;
    }

    Node* max(Node* node) {
        if (node != nullptr) {
            while (node->right != nullptr) {
                node = node->right;
            }
        }
        return node;
    }

    void print() {
        print(root_);
        cout << endl;
    }

    int size() const {
        return size_;
    }

    void clear() {
        clear(root_);
        root_ = nullptr;
        size_ = 0;
    }

    Node* find(const T& val) {
        Node* node = root_;
        while (node != nullptr && node->value != val) {
            node = node->value > val ? node->left : node->right;
        }
        return node;
    }

    Node* begin() {
        return min(root_);
    }

    Node* end() {
        return max(root_);
    }

    bool operator==(const Set& other) {
        return size_ == other.size_ ? compare(min(root_), min(other.root_)) : false;
    }

    bool operator!=(const Set& other) {
        return !(*this == other);
    }

    ~Set() {
        clear(root_);
    }

private:

    // вариант сравнения деревьев на случай разной топологии но одинакового размера
    bool compare(Node* a, Node* b) {
        if (a == nullptr && b == nullptr) {
            return true;
        }
        return  a->value == b->value && compare(next(a), next(b));
    }

    Node* next(Node* node) {
        if (node != nullptr) {
            if (node->right != nullptr) {
                return min(node->right);
            }
            Node* temp = node->parent;
            while (temp != nullptr && node->value > temp->value) {
                temp = temp->parent;
            }
            return temp;
        }
        return node;
    }

    Node* prev(Node* node) {
        if (node != nullptr) {
            if (node->left != nullptr) {
                return max(node->left);
            }
            Node* temp = node->parent;
            while (temp != nullptr && node->value < temp->value) {
                temp = temp->parent;
            }
            return temp;
        }
        return node;
    }

    Node* copy(Node* node, Node* parent) {
        if (node == nullptr) {
            return nullptr;
        }
        Node* temp = new Node{ node->value, nullptr, nullptr, parent };
        temp->left = copy(node->left, temp);
        temp->right = copy(node->right, temp);
        return temp;
    }

    void clear(Node* node) {
        if (node != nullptr) {
            clear(node->left);
            clear(node->right);
            delete node;
        }
    }

    void print(Node* node) {
        if (node != nullptr) {
            print(node->left);
            cout << node->value << " ";
            // раскомментировать для проверки построения дерева
           /* cout << " value " << node->value << " ";
            if (node->parent) {
                cout << " parent " << node->parent->value;
            }
            else {
                cout << '\t';
            }
            if (node->left) {
                cout << " left " << node->left->value;
            }
            else {
                cout << '\t';
            }
            if (node->right) {
                cout << " right " << node->right->value;
            }
            else {
                cout << '\t';
            }
            cout << " " << node << endl;*/
            print(node->right);
        }
    }

    Node* root_;
    int size_;
};

int main() {
    setlocale(LC_ALL, "ru");

    // проверить функционал каждого класса

}