//======================================================
// Author      : Omar_Hafez
// Created     : 31 July 2022 (Sunday)  5:19:10 AM
//======================================================

#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>

template <typename T>
class List {
    
    public:
        struct Node {
            T value;
            std::shared_ptr<Node> front, back;
            Node (T data, std::shared_ptr<Node> ptr, std::shared_ptr<Node> ptr2) 
                : value(data), front(ptr), back(ptr2) {}
        };

    private:
        size_t elementsCount = 0;
        std::shared_ptr<Node> begin_ptr, end_ptr, itr, tmp_ptr, header, teller;
    
    public:
        List() :
            header(std::make_shared<Node>((T)NULL, nullptr, nullptr)),
            teller(std::make_shared<Node>((T)NULL, nullptr, nullptr)) {}

        struct Iterator {
            std::shared_ptr<Node> operator*() const { return m_ptr; }

            Iterator operator++(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->front) || indxOfPtr < 0) {
                    indxOfPtr++;
                    return *this;
                }
                Iterator tmp = *this; 
                (*this) = m_ptr->front; 
                return tmp; 
            }

            Iterator operator--(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->back) || indxOfPtr > 0) {
                    indxOfPtr--;
                    return *this;
                }
                Iterator tmp = *this; 
                (*this) = m_ptr->back; 
                return tmp; 
            }

            friend bool operator== (const Iterator& a, const Iterator& b) { return a.m_ptr == b.m_ptr; };
            friend bool operator!= (const Iterator& a, const Iterator& b) { return a.m_ptr != b.m_ptr; };     

            std::shared_ptr<Node> m_ptr;
            size_t indxOfPtr;
            Iterator(std::shared_ptr<Node> ptr) : m_ptr(ptr), indxOfPtr(0) {}
        };

        struct RIterator {
            std::shared_ptr<Node> operator*() const { return m_ptr; }

            RIterator operator++(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->back) || indxOfPtr > 0) {
                    indxOfPtr--;
                    return *this;
                }
                RIterator tmp = *this; 
                (*this) = m_ptr->back; 
                return tmp; 
            }

            RIterator operator--(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->front) || indxOfPtr < 0) {
                    indxOfPtr++;
                    return *this;
                }
                RIterator tmp = *this; 
                (*this) = m_ptr->front; 
                return tmp; 
            }

            Iterator to_Iterator() {
                return Iterator(m_ptr->front);
            }

            friend bool operator== (const RIterator& a, const RIterator& b) { return a.m_ptr == b.m_ptr; };
            friend bool operator!= (const RIterator& a, const RIterator& b) { return a.m_ptr != b.m_ptr; };     

            std::shared_ptr<Node> m_ptr;
            size_t indxOfPtr;
            RIterator(std::shared_ptr<Node> ptr) : m_ptr(ptr), indxOfPtr(0) {}
        };

        void advance(List<T>::Iterator &it, size_t val) {
            while(*it && it != end() && val > 0) {
                it++;
                val--;
            }
        }

        void createFirstNode(T t) {
            begin_ptr = std::make_shared<Node>(t, nullptr, nullptr);
            end_ptr = begin_ptr;
            
            header->front = begin_ptr;
            begin_ptr->back = header;

            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount++;
        }

        Iterator begin() { return Iterator(begin_ptr); }

        Iterator end()   { 
            if(!end_ptr) return Iterator(end_ptr);
            return Iterator(end_ptr->front); 
        } 

        RIterator rbegin() { 
            return RIterator(end_ptr); 
        }

        RIterator rend() { 
            if(!begin_ptr) return RIterator(begin_ptr);
            return RIterator(begin_ptr->back); 
        } 

        enum ListOpStatus { FailedListEmpty = -1, FailedListFull = -2, FailedInvalidIterator = -3, OK = 1 };

        ListOpStatus assign(T t, size_t count) {
            if(count == 0) return OK;
            begin_ptr = std::make_shared<Node>(t, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            itr = begin_ptr;
            for(int i = 1; i < count; i++) {
                itr->front = std::make_shared<Node>(t, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
            }

            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount = count;
            end_ptr = itr;
            return OK;
        }

        // assigning from another list
        ListOpStatus assign(List<T>::Iterator it1, List<T>::Iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> ((*it1)->value, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>((*it1)->value, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        // assigning from another reversed list
        ListOpStatus assign(List<T>::RIterator it1, List<T>::RIterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> ((*it1)->value, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>((*it1)->value, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        // assigning from vector
        ListOpStatus assign(typename std::vector<T>::iterator it1, typename std::vector<T>::iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> (*it1, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>(*it1, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        // assigning from reversed vector
        ListOpStatus assign(typename std::vector<T>::reverse_iterator it1, typename std::vector<T>::reverse_iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> (*it1, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>(*it1, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        ListOpStatus push_back(T t) {
            if(empty()) {
                createFirstNode(t);
                return OK;
            } 
            tmp_ptr = end_ptr;
            end_ptr->front = std::make_shared<Node>(t, nullptr, nullptr);
            end_ptr = end_ptr->front;
            end_ptr->back = tmp_ptr;

            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount++;
            return OK;
        }

        ListOpStatus push_front(T t) {
            if(empty()) {
                createFirstNode(t);
                return OK;
            } 
            tmp_ptr = begin_ptr;
            begin_ptr->back = std::make_shared<Node>(t, nullptr, nullptr);
            begin_ptr = begin_ptr->back;
            begin_ptr->front = tmp_ptr;

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount++;
            return OK;
        }

        ListOpStatus pop_back() {
            if(elementsCount == 1) {
                clear();
                return OK;
            }
            if(empty()) {
                return FailedListEmpty;
            }
            end_ptr = end_ptr->back;
            end_ptr->front = nullptr;

            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount--;
            return OK;
        }

        ListOpStatus pop_front() {
            if(elementsCount == 1) {
                clear();
                return OK;
            }
            if(empty()) {
                return FailedListEmpty;
            }
            begin_ptr = begin_ptr->front;
            begin_ptr->back = nullptr;
            
            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount--;
            return OK;
        }

        ListOpStatus swap(List<T>::Iterator it1, List<T>::Iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            T tmp = (*it1)->value;
            (*it1)->value = (*it2)->value;
            (*it2)->value = tmp;
            return OK;
        }

        ListOpStatus swap(List<T>::RIterator it1, List<T>::RIterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            return swap(it1.to_Iterator(), it2.to_Iterator());
        }

        ListOpStatus insert(List<T>::Iterator it, T t) {
            if(empty()) {
                createFirstNode(t);
                return OK;;
            }

            if(*it == begin_ptr) {
                push_front(t);
                return OK;
            }

            if(*it == end()) {
                push_back(t);
                return OK;
            }

            if(!(*it)) return FailedInvalidIterator;

            tmp_ptr = std::make_shared<Node>(t, (*it), (*it)->back);
            tmp_ptr->back->front = tmp_ptr;
            (*it)->back = tmp_ptr;
            elementsCount++;
            return OK;
        }

        ListOpStatus insert(List<T>::RIterator it, T t) {
            return insert(it.to_Iterator(), t);
        }

        ListOpStatus sort() {
            T a[elementsCount];
            size_t ind = 0;
            for(auto it = begin(); it != end(); it++) {
                a[ind++] = (*it)->value;
            }
            std::sort(a, a+elementsCount);
            clear();
            for(T x : a) {
                push_back(x);
            }
            return OK;
        }

        ListOpStatus unique() {
            if(empty()) return OK;
            T a[elementsCount];
            size_t ind = 0;
            for(auto it = begin(); it != end(); it++) {
                a[ind++] = (*it)->value;
            }
            std::sort(a, a+elementsCount);
            size_t sz = elementsCount;
            clear();
            push_back(a[0]);
            for(size_t i = 1; i < sz; i++) {
                if(a[i] == a[i-1]) continue;
                push_back(a[i]);
            }
            return OK;
        }

        ListOpStatus erase(List<T>::Iterator it) {
            if(!(*it) || it == end()) return FailedInvalidIterator;
            if(empty()) return OK;
            if(*it == header || *it == teller) return FailedInvalidIterator;
            if(elementsCount == 1) {
                clear();
                return OK;
            }
            itr = *it;
            if(itr == begin_ptr) {
                pop_front();
                return OK;
            }
            if(itr == end_ptr) {
                pop_back();
                return OK;
            }
            tmp_ptr = itr->front;
            auto tmp = itr->back;
            tmp->front = tmp_ptr;
            tmp_ptr->back = tmp; 
            elementsCount--;
            return OK;
        }

        ListOpStatus erase(List<T>::RIterator it) {
            return erase(List<T>::Iterator((*it)->front));
        }

        ListOpStatus erase(List<T>::Iterator it1, List<T>::Iterator it2) {
            while(it1 != it2) {
                erase(it1);
                it1++;
            }
            return OK;
        }

        ListOpStatus erase(List<T>::RIterator it1, List<T>::RIterator it2) {
            return(erase(it2.to_Iterator(), it1.to_Iterator()));
        }

        ListOpStatus remove_if(bool (*function) (T& t)) {
            for(itr = begin_ptr; itr; itr = itr->front) {
                if((*function) (itr->value)) {
                    erase(List<T>::Iterator(itr));
                    if(empty()) return OK;
                }
            }
            return OK;
        }

        ListOpStatus remove(T t) {
            for(itr = begin_ptr; itr; itr = itr->front) {
                if(itr->value == t) {
                    erase(List<T>::Iterator(itr));
                    if(empty()) return OK;
                }
            }
            return OK;
        }

        void clear() {
            begin_ptr = nullptr;
            end_ptr = nullptr;
            itr = nullptr;
            tmp_ptr = nullptr;
            teller->back = nullptr;
            header->front = nullptr;
            elementsCount = 0;
        }

        bool empty() const {
            return elementsCount == 0;
        } 

        bool full() const {
            return 0;
        }

        int size() const {
            return elementsCount;
        }

        void traverseList(void (*function) (T& t)) {
            for(itr = begin_ptr; itr; itr = itr->front) {
                (*function)(itr->value);
            }
        }
};

//======================================================
// Author      : Omar_Hafez
// Created     : 31 July 2022 (Sunday)  5:19:10 AM
//======================================================

#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>

template <typename T>
class List {
    
    public:
        struct Node {
            T value;
            std::shared_ptr<Node> front, back;
            Node (T data, std::shared_ptr<Node> ptr, std::shared_ptr<Node> ptr2) 
                : value(data), front(ptr), back(ptr2) {}
        };

    private:
        int elementsCount = 0;
        std::shared_ptr<Node> begin_ptr, end_ptr, itr, tmp_ptr, header, teller;
    
    public:
        List() :
            header(std::make_shared<Node>((T)NULL, nullptr, nullptr)),
            teller(std::make_shared<Node>((T)NULL, nullptr, nullptr)) {}

        struct Iterator {
            std::shared_ptr<Node> operator*() const { return m_ptr; }

            Iterator operator++(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->front) || indxOfPtr < 0) {
                    indxOfPtr++;
                    return *this;
                }
                Iterator tmp = *this; 
                (*this) = m_ptr->front; 
                return tmp; 
            }

            Iterator operator--(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->back) || indxOfPtr > 0) {
                    indxOfPtr--;
                    return *this;
                }
                Iterator tmp = *this; 
                (*this) = m_ptr->back; 
                return tmp; 
            }

            friend bool operator== (const Iterator& a, const Iterator& b) { return a.m_ptr == b.m_ptr; };
            friend bool operator!= (const Iterator& a, const Iterator& b) { return a.m_ptr != b.m_ptr; };     

            std::shared_ptr<Node> m_ptr;
            int indxOfPtr;
            Iterator(std::shared_ptr<Node> ptr) : m_ptr(ptr), indxOfPtr(0) {}
        };

        struct RIterator {
            std::shared_ptr<Node> operator*() const { return m_ptr; }

            RIterator operator++(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->back) || indxOfPtr > 0) {
                    indxOfPtr--;
                    return *this;
                }
                RIterator tmp = *this; 
                (*this) = m_ptr->back; 
                return tmp; 
            }

            RIterator operator--(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->front) || indxOfPtr < 0) {
                    indxOfPtr++;
                    return *this;
                }
                RIterator tmp = *this; 
                (*this) = m_ptr->front; 
                return tmp; 
            }

            Iterator to_Iterator() {
                return Iterator(m_ptr->front);
            }

            friend bool operator== (const RIterator& a, const RIterator& b) { return a.m_ptr == b.m_ptr; };
            friend bool operator!= (const RIterator& a, const RIterator& b) { return a.m_ptr != b.m_ptr; };     

            std::shared_ptr<Node> m_ptr;
            int indxOfPtr;
            RIterator(std::shared_ptr<Node> ptr) : m_ptr(ptr), indxOfPtr(0) {}
        };

        void advance(List<T>::Iterator &it, int val) {
            while(*it && it != end() && val > 0) {
                it++;
                val--;
            }
        }

        void createFirstNode(T t) {
            begin_ptr = std::make_shared<Node>(t, nullptr, nullptr);
            end_ptr = begin_ptr;
            
            header->front = begin_ptr;
            begin_ptr->back = header;

            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount++;
        }

        Iterator begin() { return Iterator(begin_ptr); }

        Iterator end()   { 
            if(!end_ptr) return Iterator(end_ptr);
            return Iterator(end_ptr->front); 
        } 

        RIterator rbegin() { 
            return RIterator(end_ptr); 
        }

        RIterator rend() { 
            if(!begin_ptr) return RIterator(begin_ptr);
            return RIterator(begin_ptr->back); 
        } 

        enum ListOpStatus { FailedListEmpty = -1, FailedListFull = -2, FailedInvalidIterator = -3, OK = 1 };

        ListOpStatus assign(T t, int count) {
            if(count == 0) return OK;
            begin_ptr = std::make_shared<Node>(t, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            itr = begin_ptr;
            for(int i = 1; i < count; i++) {
                itr->front = std::make_shared<Node>(t, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
            }

            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount = count;
            end_ptr = itr;
            return OK;
        }

        // assigning from another list
        ListOpStatus assign(List<T>::Iterator it1, List<T>::Iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> ((*it1)->value, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>((*it1)->value, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        // assigning from another reversed list
        ListOpStatus assign(List<T>::RIterator it1, List<T>::RIterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> ((*it1)->value, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>((*it1)->value, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        // assigning from vector
        ListOpStatus assign(typename std::vector<T>::iterator it1, typename std::vector<T>::iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> (*it1, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>(*it1, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        // assigning from reversed vector
        ListOpStatus assign(typename std::vector<T>::reverse_iterator it1, typename std::vector<T>::reverse_iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> (*it1, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>(*it1, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        ListOpStatus push_back(T t) {
            if(empty()) {
                createFirstNode(t);
                return OK;
            } 
            tmp_ptr = end_ptr;
            end_ptr->front = std::make_shared<Node>(t, nullptr, nullptr);
            end_ptr = end_ptr->front;
            end_ptr->back = tmp_ptr;

            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount++;
            return OK;
        }

        ListOpStatus push_front(T t) {
            if(empty()) {
                createFirstNode(t);
                return OK;
            } 
            tmp_ptr = begin_ptr;
            begin_ptr->back = std::make_shared<Node>(t, nullptr, nullptr);
            begin_ptr = begin_ptr->back;
            begin_ptr->front = tmp_ptr;

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount++;
            return OK;
        }

        ListOpStatus pop_back() {
            if(elementsCount == 1) {
                clear();
                return OK;
            }
            if(empty()) {
                return FailedListEmpty;
            }
            end_ptr = end_ptr->back;
            end_ptr->front = nullptr;

            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount--;
            return OK;
        }

        ListOpStatus pop_front() {
            if(elementsCount == 1) {
                clear();
                return OK;
            }
            if(empty()) {
                return FailedListEmpty;
            }
            begin_ptr = begin_ptr->front;
            begin_ptr->back = nullptr;
            
            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount--;
            return OK;
        }

        ListOpStatus swap(List<T>::Iterator it1, List<T>::Iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            T tmp = (*it1)->value;
            (*it1)->value = (*it2)->value;
            (*it2)->value = tmp;
            return OK;
        }

        ListOpStatus swap(List<T>::RIterator it1, List<T>::RIterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            return swap(it1.to_Iterator(), it2.to_Iterator());
        }

        ListOpStatus insert(List<T>::Iterator it, T t) {
            if(empty()) {
                createFirstNode(t);
                return OK;;
            }

            if(*it == begin_ptr) {
                push_front(t);
                return OK;
            }

            if(*it == end()) {
                push_back(t);
                return OK;
            }

            if(!(*it)) return FailedInvalidIterator;

            tmp_ptr = std::make_shared<Node>(t, (*it), (*it)->back);
            tmp_ptr->back->front = tmp_ptr;
            (*it)->back = tmp_ptr;
            elementsCount++;
            return OK;
        }

        ListOpStatus insert(List<T>::RIterator it, T t) {
            return insert(it.to_Iterator(), t);
        }

        ListOpStatus sort() {
            T a[elementsCount];
            int ind = 0;
            for(auto it = begin(); it != end(); it++) {
                a[ind++] = (*it)->value;
            }
            std::sort(a, a+elementsCount);
            clear();
            for(int x : a) {
                push_back(x);
            }
            return OK;
        }

        ListOpStatus unique() {
            if(empty()) return OK;
            T a[elementsCount];
            int ind = 0;
            for(auto it = begin(); it != end(); it++) {
                a[ind++] = (*it)->value;
            }
            std::sort(a, a+elementsCount);
            int sz = elementsCount;
            clear();
            push_back(a[0]);
            for(int i = 1; i < sz; i++) {
                if(a[i] == a[i-1]) continue;
                push_back(a[i]);
            }
            return OK;
        }

        ListOpStatus erase(List<T>::Iterator it) {
            if(!(*it) || it == end()) return FailedInvalidIterator;
            if(empty()) return OK;
            if(*it == header || *it == teller) return FailedInvalidIterator;
            if(elementsCount == 1) {
                clear();
                return OK;
            }
            itr = *it;
            if(itr == begin_ptr) {
                pop_front();
                return OK;
            }
            if(itr == end_ptr) {
                pop_back();
                return OK;
            }
            tmp_ptr = itr->front;
            auto tmp = itr->back;
            tmp->front = tmp_ptr;
            tmp_ptr->back = tmp; 
            elementsCount--;
            return OK;
        }

        ListOpStatus erase(List<T>::RIterator it) {
            return erase(List<T>::Iterator((*it)->front));
        }

        ListOpStatus erase(List<T>::Iterator it1, List<T>::Iterator it2) {
            while(it1 != it2) {
                erase(it1);
                it1++;
            }
            return OK;
        }

        ListOpStatus erase(List<T>::RIterator it1, List<T>::RIterator it2) {
            return(erase(it2.to_Iterator(), it1.to_Iterator()));
        }

        ListOpStatus remove_if(bool (*function) (T& t)) {
            for(itr = begin_ptr; itr; itr = itr->front) {
                if((*function) (itr->value)) {
                    erase(List<T>::Iterator(itr));
                    if(empty()) return OK;
                }
            }
            return OK;
        }

        ListOpStatus remove(T t) {
            for(itr = begin_ptr; itr; itr = itr->front) {
                if(itr->value == t) {
                    erase(List<T>::Iterator(itr));
                    if(empty()) return OK;
                }
            }
            return OK;
        }

        void clear() {
            begin_ptr = nullptr;
            end_ptr = nullptr;
            itr = nullptr;
            tmp_ptr = nullptr;
            teller->back = nullptr;
            header->front = nullptr;
            elementsCount = 0;
        }

        bool empty() const {
            return elementsCount == 0;
        } 

        bool full() const {
            return 0;
        }

        int size() const {
            return elementsCount;
        }

        void traverseList(void (*function) (T& t)) {
            for(itr = begin_ptr; itr; itr = itr->front) {
                (*function)(itr->value);
            }
        }
};

//======================================================
// Author      : Omar_Hafez
// Created     : 31 July 2022 (Sunday)  5:19:10 AM
//======================================================

#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>

template <typename T>
class List {
    
    public:
        struct Node {
            T value;
            std::shared_ptr<Node> front, back;
            Node (T data, std::shared_ptr<Node> ptr, std::shared_ptr<Node> ptr2) 
                : value(data), front(ptr), back(ptr2) {}
        };

    private:
        int elementsCount = 0;
        std::shared_ptr<Node> begin_ptr, end_ptr, itr, tmp_ptr, header, teller;
    
    public:
        List() :
            header(std::make_shared<Node>((T)NULL, nullptr, nullptr)),
            teller(std::make_shared<Node>((T)NULL, nullptr, nullptr)) {}

        struct Iterator {
            std::shared_ptr<Node> operator*() const { return m_ptr; }

            Iterator operator++(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->front) || indxOfPtr < 0) {
                    indxOfPtr++;
                    return *this;
                }
                Iterator tmp = *this; 
                (*this) = m_ptr->front; 
                return tmp; 
            }

            Iterator operator--(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->back) || indxOfPtr > 0) {
                    indxOfPtr--;
                    return *this;
                }
                Iterator tmp = *this; 
                (*this) = m_ptr->back; 
                return tmp; 
            }

            friend bool operator== (const Iterator& a, const Iterator& b) { return a.m_ptr == b.m_ptr; };
            friend bool operator!= (const Iterator& a, const Iterator& b) { return a.m_ptr != b.m_ptr; };     

            std::shared_ptr<Node> m_ptr;
            int indxOfPtr;
            Iterator(std::shared_ptr<Node> ptr) : m_ptr(ptr), indxOfPtr(0) {}
        };

        struct RIterator {
            std::shared_ptr<Node> operator*() const { return m_ptr; }

            RIterator operator++(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->back) || indxOfPtr > 0) {
                    indxOfPtr--;
                    return *this;
                }
                RIterator tmp = *this; 
                (*this) = m_ptr->back; 
                return tmp; 
            }

            RIterator operator--(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->front) || indxOfPtr < 0) {
                    indxOfPtr++;
                    return *this;
                }
                RIterator tmp = *this; 
                (*this) = m_ptr->front; 
                return tmp; 
            }

            Iterator to_Iterator() {
                return Iterator(m_ptr->front);
            }

            friend bool operator== (const RIterator& a, const RIterator& b) { return a.m_ptr == b.m_ptr; };
            friend bool operator!= (const RIterator& a, const RIterator& b) { return a.m_ptr != b.m_ptr; };     

            std::shared_ptr<Node> m_ptr;
            int indxOfPtr;
            RIterator(std::shared_ptr<Node> ptr) : m_ptr(ptr), indxOfPtr(0) {}
        };

        void advance(List<T>::Iterator &it, int val) {
            while(*it && it != end() && val > 0) {
                it++;
                val--;
            }
        }

        void createFirstNode(T t) {
            begin_ptr = std::make_shared<Node>(t, nullptr, nullptr);
            end_ptr = begin_ptr;
            
            header->front = begin_ptr;
            begin_ptr->back = header;

            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount++;
        }

        Iterator begin() { return Iterator(begin_ptr); }

        Iterator end()   { 
            if(!end_ptr) return Iterator(end_ptr);
            return Iterator(end_ptr->front); 
        } 

        RIterator rbegin() { 
            return RIterator(end_ptr); 
        }

        RIterator rend() { 
            if(!begin_ptr) return RIterator(begin_ptr);
            return RIterator(begin_ptr->back); 
        } 

        enum ListOpStatus { FailedListEmpty = -1, FailedListFull = -2, FailedInvalidIterator = -3, OK = 1 };

        ListOpStatus assign(T t, int count) {
            if(count == 0) return OK;
            begin_ptr = std::make_shared<Node>(t, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            itr = begin_ptr;
            for(int i = 1; i < count; i++) {
                itr->front = std::make_shared<Node>(t, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
            }

            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount = count;
            end_ptr = itr;
            return OK;
        }

        // assigning from another list
        ListOpStatus assign(List<T>::Iterator it1, List<T>::Iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> ((*it1)->value, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>((*it1)->value, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        // assigning from another reversed list
        ListOpStatus assign(List<T>::RIterator it1, List<T>::RIterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> ((*it1)->value, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>((*it1)->value, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        // assigning from vector
        ListOpStatus assign(typename std::vector<T>::iterator it1, typename std::vector<T>::iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> (*it1, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>(*it1, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        // assigning from reversed vector
        ListOpStatus assign(typename std::vector<T>::reverse_iterator it1, typename std::vector<T>::reverse_iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> (*it1, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>(*it1, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        ListOpStatus push_back(T t) {
            if(empty()) {
                createFirstNode(t);
                return OK;
            } 
            tmp_ptr = end_ptr;
            end_ptr->front = std::make_shared<Node>(t, nullptr, nullptr);
            end_ptr = end_ptr->front;
            end_ptr->back = tmp_ptr;

            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount++;
            return OK;
        }

        ListOpStatus push_front(T t) {
            if(empty()) {
                createFirstNode(t);
                return OK;
            } 
            tmp_ptr = begin_ptr;
            begin_ptr->back = std::make_shared<Node>(t, nullptr, nullptr);
            begin_ptr = begin_ptr->back;
            begin_ptr->front = tmp_ptr;

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount++;
            return OK;
        }

        ListOpStatus pop_back() {
            if(elementsCount == 1) {
                clear();
                return OK;
            }
            if(empty()) {
                return FailedListEmpty;
            }
            end_ptr = end_ptr->back;
            end_ptr->front = nullptr;

            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount--;
            return OK;
        }

        ListOpStatus pop_front() {
            if(elementsCount == 1) {
                clear();
                return OK;
            }
            if(empty()) {
                return FailedListEmpty;
            }
            begin_ptr = begin_ptr->front;
            begin_ptr->back = nullptr;
            
            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount--;
            return OK;
        }

        ListOpStatus swap(List<T>::Iterator it1, List<T>::Iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            T tmp = (*it1)->value;
            (*it1)->value = (*it2)->value;
            (*it2)->value = tmp;
            return OK;
        }

        ListOpStatus swap(List<T>::RIterator it1, List<T>::RIterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            return swap(it1.to_Iterator(), it2.to_Iterator());
        }

        ListOpStatus insert(List<T>::Iterator it, T t) {
            if(empty()) {
                createFirstNode(t);
                return OK;;
            }

            if(*it == begin_ptr) {
                push_front(t);
                return OK;
            }

            if(*it == end()) {
                push_back(t);
                return OK;
            }

            if(!(*it)) return FailedInvalidIterator;

            tmp_ptr = std::make_shared<Node>(t, (*it), (*it)->back);
            tmp_ptr->back->front = tmp_ptr;
            (*it)->back = tmp_ptr;
            elementsCount++;
            return OK;
        }

        ListOpStatus insert(List<T>::RIterator it, T t) {
            return insert(it.to_Iterator(), t);
        }

        ListOpStatus sort() {
            T a[elementsCount];
            int ind = 0;
            for(auto it = begin(); it != end(); it++) {
                a[ind++] = (*it)->value;
            }
            std::sort(a, a+elementsCount);
            clear();
            for(int x : a) {
                push_back(x);
            }
            return OK;
        }

        ListOpStatus unique() {
            if(empty()) return OK;
            T a[elementsCount];
            int ind = 0;
            for(auto it = begin(); it != end(); it++) {
                a[ind++] = (*it)->value;
            }
            std::sort(a, a+elementsCount);
            int sz = elementsCount;
            clear();
            push_back(a[0]);
            for(int i = 1; i < sz; i++) {
                if(a[i] == a[i-1]) continue;
                push_back(a[i]);
            }
            return OK;
        }

        ListOpStatus erase(List<T>::Iterator it) {
            if(!(*it) || it == end()) return FailedInvalidIterator;
            if(empty()) return OK;
            if(*it == header || *it == teller) return FailedInvalidIterator;
            if(elementsCount == 1) {
                clear();
                return OK;
            }
            itr = *it;
            if(itr == begin_ptr) {
                pop_front();
                return OK;
            }
            if(itr == end_ptr) {
                pop_back();
                return OK;
            }
            tmp_ptr = itr->front;
            auto tmp = itr->back;
            tmp->front = tmp_ptr;
            tmp_ptr->back = tmp; 
            elementsCount--;
            return OK;
        }

        ListOpStatus erase(List<T>::RIterator it) {
            return erase(List<T>::Iterator((*it)->front));
        }

        ListOpStatus erase(List<T>::Iterator it1, List<T>::Iterator it2) {
            while(it1 != it2) {
                erase(it1);
                it1++;
            }
            return OK;
        }

        ListOpStatus erase(List<T>::RIterator it1, List<T>::RIterator it2) {
            return(erase(it2.to_Iterator(), it1.to_Iterator()));
        }

        ListOpStatus remove_if(bool (*function) (T& t)) {
            for(itr = begin_ptr; itr; itr = itr->front) {
                if((*function) (itr->value)) {
                    erase(List<T>::Iterator(itr));
                    if(empty()) return OK;
                }
            }
            return OK;
        }

        ListOpStatus remove(T t) {
            for(itr = begin_ptr; itr; itr = itr->front) {
                if(itr->value == t) {
                    erase(List<T>::Iterator(itr));
                    if(empty()) return OK;
                }
            }
            return OK;
        }

        void clear() {
            begin_ptr = nullptr;
            end_ptr = nullptr;
            itr = nullptr;
            tmp_ptr = nullptr;
            teller->back = nullptr;
            header->front = nullptr;
            elementsCount = 0;
        }

        bool empty() const {
            return elementsCount == 0;
        } 

        bool full() const {
            return 0;
        }

        int size() const {
            return elementsCount;
        }

        void traverseList(void (*function) (T& t)) {
            for(itr = begin_ptr; itr; itr = itr->front) {
                (*function)(itr->value);
            }
        }
};

//======================================================
// Author      : Omar_Hafez
// Created     : 31 July 2022 (Sunday)  5:19:10 AM
//======================================================

#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>

template <typename T>
class List {
    
    public:
        struct Node {
            T value;
            std::shared_ptr<Node> front, back;
            Node (T data, std::shared_ptr<Node> ptr, std::shared_ptr<Node> ptr2) 
                : value(data), front(ptr), back(ptr2) {}
        };

    private:
        size_t elementsCount = 0;
        std::shared_ptr<Node> begin_ptr, end_ptr, itr, tmp_ptr, header, teller;
    
    public:
        List() :
            header(std::make_shared<Node>((T)NULL, nullptr, nullptr)),
            teller(std::make_shared<Node>((T)NULL, nullptr, nullptr)) {}

        struct Iterator {
            std::shared_ptr<Node> operator*() const { return m_ptr; }

            Iterator operator++(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->front) || indxOfPtr < 0) {
                    indxOfPtr++;
                    return *this;
                }
                Iterator tmp = *this; 
                (*this) = m_ptr->front; 
                return tmp; 
            }

            Iterator operator--(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->back) || indxOfPtr > 0) {
                    indxOfPtr--;
                    return *this;
                }
                Iterator tmp = *this; 
                (*this) = m_ptr->back; 
                return tmp; 
            }

            friend bool operator== (const Iterator& a, const Iterator& b) { return a.m_ptr == b.m_ptr; };
            friend bool operator!= (const Iterator& a, const Iterator& b) { return a.m_ptr != b.m_ptr; };     

            std::shared_ptr<Node> m_ptr;
            size_t indxOfPtr;
            Iterator(std::shared_ptr<Node> ptr) : m_ptr(ptr), indxOfPtr(0) {}
        };

        struct RIterator {
            std::shared_ptr<Node> operator*() const { return m_ptr; }

            RIterator operator++(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->back) || indxOfPtr > 0) {
                    indxOfPtr--;
                    return *this;
                }
                RIterator tmp = *this; 
                (*this) = m_ptr->back; 
                return tmp; 
            }

            RIterator operator--(int) { 
                if(!m_ptr) return *this;
                if(!(m_ptr->front) || indxOfPtr < 0) {
                    indxOfPtr++;
                    return *this;
                }
                RIterator tmp = *this; 
                (*this) = m_ptr->front; 
                return tmp; 
            }

            Iterator to_Iterator() {
                return Iterator(m_ptr->front);
            }

            friend bool operator== (const RIterator& a, const RIterator& b) { return a.m_ptr == b.m_ptr; };
            friend bool operator!= (const RIterator& a, const RIterator& b) { return a.m_ptr != b.m_ptr; };     

            std::shared_ptr<Node> m_ptr;
            size_t indxOfPtr;
            RIterator(std::shared_ptr<Node> ptr) : m_ptr(ptr), indxOfPtr(0) {}
        };

        void advance(List<T>::Iterator &it, size_t val) {
            while(*it && it != end() && val > 0) {
                it++;
                val--;
            }
        }

        void createFirstNode(T t) {
            begin_ptr = std::make_shared<Node>(t, nullptr, nullptr);
            end_ptr = begin_ptr;
            
            header->front = begin_ptr;
            begin_ptr->back = header;

            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount++;
        }

        Iterator begin() { return Iterator(begin_ptr); }

        Iterator end()   { 
            if(!end_ptr) return Iterator(end_ptr);
            return Iterator(end_ptr->front); 
        } 

        RIterator rbegin() { 
            return RIterator(end_ptr); 
        }

        RIterator rend() { 
            if(!begin_ptr) return RIterator(begin_ptr);
            return RIterator(begin_ptr->back); 
        } 

        enum ListOpStatus { FailedListEmpty = -1, FailedListFull = -2, FailedInvalidIterator = -3, OK = 1 };

        ListOpStatus assign(T t, size_t count) {
            if(count == 0) return OK;
            begin_ptr = std::make_shared<Node>(t, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            itr = begin_ptr;
            for(int i = 1; i < count; i++) {
                itr->front = std::make_shared<Node>(t, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
            }

            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount = count;
            end_ptr = itr;
            return OK;
        }

        // assigning from another list
        ListOpStatus assign(List<T>::Iterator it1, List<T>::Iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> ((*it1)->value, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>((*it1)->value, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        // assigning from another reversed list
        ListOpStatus assign(List<T>::RIterator it1, List<T>::RIterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> ((*it1)->value, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>((*it1)->value, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        // assigning from vector
        ListOpStatus assign(typename std::vector<T>::iterator it1, typename std::vector<T>::iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> (*it1, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>(*it1, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        // assigning from reversed vector
        ListOpStatus assign(typename std::vector<T>::reverse_iterator it1, typename std::vector<T>::reverse_iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            begin_ptr = std::make_shared<Node> (*it1, nullptr, nullptr);

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount = 1;
            itr = begin_ptr;
            it1++;
            while(it1 != it2) {
                itr->front = std::make_shared<Node>(*it1, nullptr, nullptr);
                tmp_ptr = itr;
                itr = itr->front;
                itr->back = tmp_ptr;
                it1++;
                elementsCount++;
            }
            end_ptr = itr;
            teller->back = end_ptr;
            end_ptr->front = teller;
            return OK;
        }

        ListOpStatus push_back(T t) {
            if(empty()) {
                createFirstNode(t);
                return OK;
            } 
            tmp_ptr = end_ptr;
            end_ptr->front = std::make_shared<Node>(t, nullptr, nullptr);
            end_ptr = end_ptr->front;
            end_ptr->back = tmp_ptr;

            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount++;
            return OK;
        }

        ListOpStatus push_front(T t) {
            if(empty()) {
                createFirstNode(t);
                return OK;
            } 
            tmp_ptr = begin_ptr;
            begin_ptr->back = std::make_shared<Node>(t, nullptr, nullptr);
            begin_ptr = begin_ptr->back;
            begin_ptr->front = tmp_ptr;

            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount++;
            return OK;
        }

        ListOpStatus pop_back() {
            if(elementsCount == 1) {
                clear();
                return OK;
            }
            if(empty()) {
                return FailedListEmpty;
            }
            end_ptr = end_ptr->back;
            end_ptr->front = nullptr;

            teller->back = end_ptr;
            end_ptr->front = teller;

            elementsCount--;
            return OK;
        }

        ListOpStatus pop_front() {
            if(elementsCount == 1) {
                clear();
                return OK;
            }
            if(empty()) {
                return FailedListEmpty;
            }
            begin_ptr = begin_ptr->front;
            begin_ptr->back = nullptr;
            
            header->front = begin_ptr;
            begin_ptr->back = header;

            elementsCount--;
            return OK;
        }

        ListOpStatus swap(List<T>::Iterator it1, List<T>::Iterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            T tmp = (*it1)->value;
            (*it1)->value = (*it2)->value;
            (*it2)->value = tmp;
            return OK;
        }

        ListOpStatus swap(List<T>::RIterator it1, List<T>::RIterator it2) {
            if(!(*it1) || !(*it2)) return FailedInvalidIterator;
            return swap(it1.to_Iterator(), it2.to_Iterator());
        }

        ListOpStatus insert(List<T>::Iterator it, T t) {
            if(empty()) {
                createFirstNode(t);
                return OK;;
            }

            if(*it == begin_ptr) {
                push_front(t);
                return OK;
            }

            if(*it == end()) {
                push_back(t);
                return OK;
            }

            if(!(*it)) return FailedInvalidIterator;

            tmp_ptr = std::make_shared<Node>(t, (*it), (*it)->back);
            tmp_ptr->back->front = tmp_ptr;
            (*it)->back = tmp_ptr;
            elementsCount++;
            return OK;
        }

        ListOpStatus insert(List<T>::RIterator it, T t) {
            return insert(it.to_Iterator(), t);
        }

        ListOpStatus sort() {
            T a[elementsCount];
            size_t ind = 0;
            for(auto it = begin(); it != end(); it++) {
                a[ind++] = (*it)->value;
            }
            std::sort(a, a+elementsCount);
            clear();
            for(T x : a) {
                push_back(x);
            }
            return OK;
        }

        ListOpStatus unique() {
            if(empty()) return OK;
            T a[elementsCount];
            size_t ind = 0;
            for(auto it = begin(); it != end(); it++) {
                a[ind++] = (*it)->value;
            }
            std::sort(a, a+elementsCount);
            size_t sz = elementsCount;
            clear();
            push_back(a[0]);
            for(size_t i = 1; i < sz; i++) {
                if(a[i] == a[i-1]) continue;
                push_back(a[i]);
            }
            return OK;
        }

        ListOpStatus erase(List<T>::Iterator it) {
            if(!(*it) || it == end()) return FailedInvalidIterator;
            if(empty()) return OK;
            if(*it == header || *it == teller) return FailedInvalidIterator;
            if(elementsCount == 1) {
                clear();
                return OK;
            }
            itr = *it;
            if(itr == begin_ptr) {
                pop_front();
                return OK;
            }
            if(itr == end_ptr) {
                pop_back();
                return OK;
            }
            tmp_ptr = itr->front;
            auto tmp = itr->back;
            tmp->front = tmp_ptr;
            tmp_ptr->back = tmp; 
            elementsCount--;
            return OK;
        }

        ListOpStatus erase(List<T>::RIterator it) {
            return erase(List<T>::Iterator((*it)->front));
        }

        ListOpStatus erase(List<T>::Iterator it1, List<T>::Iterator it2) {
            while(it1 != it2) {
                erase(it1);
                it1++;
            }
            return OK;
        }

        ListOpStatus erase(List<T>::RIterator it1, List<T>::RIterator it2) {
            return(erase(it2.to_Iterator(), it1.to_Iterator()));
        }

        ListOpStatus remove_if(bool (*function) (T& t)) {
            for(itr = begin_ptr; itr; itr = itr->front) {
                if((*function) (itr->value)) {
                    erase(List<T>::Iterator(itr));
                    if(empty()) return OK;
                }
            }
            return OK;
        }

        ListOpStatus remove(T t) {
            for(itr = begin_ptr; itr; itr = itr->front) {
                if(itr->value == t) {
                    erase(List<T>::Iterator(itr));
                    if(empty()) return OK;
                }
            }
            return OK;
        }

        void clear() {
            begin_ptr = nullptr;
            end_ptr = nullptr;
            itr = nullptr;
            tmp_ptr = nullptr;
            teller->back = nullptr;
            header->front = nullptr;
            elementsCount = 0;
        }

        bool empty() const {
            return elementsCount == 0;
        } 

        bool full() const {
            return 0;
        }

        int size() const {
            return elementsCount;
        }

        void traverseList(void (*function) (T& t)) {
            for(itr = begin_ptr; itr; itr = itr->front) {
                (*function)(itr->value);
            }
        }
};