#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>
#include <list>
#pragma comment(linker, "/STACK:1488228666")

constexpr std::size_t size_of_block_allocation = (1 << 9);

class Block_Allocation
{
public:
    char* begin_place;
    std::size_t count_free_memory;
    std::size_t count_used_memory;
    using size_type = std::size_t;
    using pointer = char*;
    Block_Allocation* prev;

    Block_Allocation()
    {
        prev = nullptr;
    }
    Block_Allocation(const size_type count_memory, Block_Allocation* prev_)
    {
        begin_place = new char[count_memory];
        count_free_memory = count_memory;
        count_used_memory = 0;
        prev = prev_;
    }
    ~Block_Allocation()
    {
        if (prev != nullptr)
        {
            delete prev;
        }
        delete[] begin_place;
    }
    pointer get_current_place()
    {
        return begin_place + count_used_memory;
    }
    pointer allocate(size_type cnt)
    {
        pointer ptr = get_current_place();
        count_free_memory -= cnt;
        count_used_memory += cnt;
        return ptr;
    }
    void deallocate(size_type cnt)
    {

    }
};

class Universal_Allocator
{
public:
    Block_Allocation* head;
    //std::vector<Block_Allocation*> blocks;
public:
    typedef std::size_t size_type;
    Universal_Allocator()
    {
        head = nullptr;
    }
    ~Universal_Allocator()
    {
        delete head;
        //for (auto block : blocks)
        //{
        //  delete block;
        //}
    }
    template < typename T >
    T* allocate(const size_type count_object)
    {
        if (head != nullptr && (head->count_free_memory) >= count_object * sizeof(T))
        {
            return reinterpret_cast<T*>(head->allocate(count_object * sizeof(T)));
        }
        else
        {
            Block_Allocation* new_block = new Block_Allocation(std::max(count_object * sizeof(T), size_of_block_allocation), head);
            head = new_block;
            //blocks.push_back(new_block);
            return reinterpret_cast<T*>(head->allocate(count_object * sizeof(T)));
        }
        /*pointer ptr = blocks.back()->get_current_place();
        if (blocks.back()->count_free_memory < size_of(T))
        {
        Block_Allocation* block = new Block_Allocation;
        //ptr = &block;
        blocks.push_back(*block);
        ptr = &blocks.back()->;
        }
        while (count_object > 0)
        {
        size_type can_write = std::min(count_object, (blocks.back()->count_free_memory) / size_of(T));
        blocks.back()->allocate(can_write * size_of(T));
        count_object -= can_write;
        if (count_object != 0)
        {
        Block_Allocation* block = new Block_Allocation;
        blocks.push_back(*block);
        }
        }
        return ptr;
        */
    }
};

template < typename T >
class Stack_Allocator
{
public:
    std::shared_ptr<Universal_Allocator> allocator;
public:
    using pointer = T*;
    using size_type = std::size_t;
    using value_type = T;
    template <typename U>
    struct rebind
    {
        typedef Stack_Allocator<U> other;
    };


    //template <typename U>
    //using rebind = Stack_Allocator<U>;

    Stack_Allocator() : allocator(std::make_shared<Universal_Allocator>())
    {
    }
    template < class U >
    Stack_Allocator(const Stack_Allocator<U>& other) : allocator(other.allocator) {};
    ~Stack_Allocator()
    {

    }
    pointer allocate(size_type count_object)
    {
        return allocator->allocate<T>(count_object);
    }
    void deallocate(pointer ptr, size_type object)
    {

    }
};

template <typename T>
T* get_xor_address(T* first, T* second)
{
    return reinterpret_cast<T*>(reinterpret_cast<uintptr_t>(first) ^ reinterpret_cast<uintptr_t>(second));
}


template <typename T>
class node
{
private:
    node<T>* xor_neighbours;
    T val;
public:
    node<T>(T value)
    {
        val = value;
    }
    node<T>(T value, node<T>* prev_value = nullptr, node* next_value = nullptr)
    {
        val = value;
        xor_neighbours = get_xor_address(prev_value, next_value);
    }
    node<T>* get_next(node<T>* pred)
    {
        return xor_address(pred, xor_neighbours);
    }
    node<T>* get_prev(node<T>* next)
    {
        return xor_address(next, xor_neighbours);
    }
    void update(node<T>* other)
    {
        if (this != nullptr)
        {
            xor_neighbours ^= other;
        }
    }

};

template <typename T>
class Xor_List_iterator : public std::iterator < std::bidirectional_iterator_tag, T>
{
private:
    node<T>* current_node;
    node<T>* prev_node;
public:
    Xor_List_iterator(const node<T>* current_node_, const node<T>* prev_node_) : current_node(current_node_), prev_node(prev_node_)
    {

    }
    Xor_List_iterator& operator=(const Xor_List_iterator& it)
    {
        current_node = it.current_node;
        prev_node = it.prev_node;
        return (*this);
    }
    bool operator==(const Xor_List_iterator& it) const
    {
        return (current_node == it.current_node && prev_node == it.prev_node);
    }
    bool operator!=(const Xor_List_iterator& it) const
    {
        return !(current_node == it.current_node && prev_node == it.prev_node);
    }
    T& operator*()
    {
        return (*current_node);
    }
    T* operator->()
    {
        return current_node;
    }
    // a b c d e
    Xor_List_iterator& operator++()
    {
        node<T>* new_current_code = get_xor_address<node<T>>(current_node->xor_neighbours, prev_node);
        node<T>* new_current_node = reinterpret_cast<node<T>*>(reinterpret_cast<uintptr_t>(current_node->xor_neighbours)
            ^ (reinterpret_cast<uintptr_t>(prev_node)));
        prev_node = current_node;
        current_node = new_current_node;
        return (*this);
    }

    Xor_List_iterator operator++(int)
    {
        Xor_List_iterator it = *this;
        (*this).operator++();
        return it;
    }
    Xor_List_iterator& operator--()
    {
        node<T>* new_prev_node = get_xor_address<node>(current_node, prev_node->xor_neighbours);
        current_node = prev_node;
        prev_node = new_prev_node;
        return (*this);
    }
    Xor_List_iterator operator--(int)
    {
        Xor_List_iterator it = *this;
        (*this).operator--();
        return it;
    }
};

//std::list<int, Stack_Allocator<int>>

//template <typename T>
//T* get_xor_address(T* first, T* second)
//{
//  return reinterpret_cast<T*>(reinterpret_cast<uintptr_t>(first) ^ reinterpret_cast<uintptr_t>(second));
//}

template < typename T, typename Allocator>
class Xor_List
{
public:
    using size_type = std::size_t;
    //using size_type = std::size;
    using iterator = Xor_List_iterator<T>;
    using const_iterator = Xor_List_iterator<const T>;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    typename Allocator::template rebind<node>::other allocator;
    node<T>* it_begin;
    node<T>* it_end;
    size_type size_list;

    explicit Xor_List(const Allocator& alloc = Allocator()) : allocator(alloc), it_begin(nullptr), it_end(nullptr), size_list(0) {};
    iterator begin()
    {
        return iterator(begin, nullptr);
    }
    iterator end()
    {
        return iterator(nullptr, end);
    }
    const_iterator begin() const
    {
        return const_iterator(begin, nullptr);
    }
    const_iterator cbegin() const
    {
        return const_iterator(begin, nullptr);
    }
    const_iterator end() const
    {
        return const_iterator(nullptr, end);
    }
    const_iterator cend() const
    {
        return const_iterator(nullptr, end);
    }
    reverse_iterator rbegin()
    {
        return reverse_iterator(end());
    }
    reverse_iterator rend()
    {
        return reverse_iterator(begin());
    }
    const const_reverse_iterator rbegin() const
    {
        return const_reverse_iterator(end());
    }
    const const_reverse_iterator crbegin() const
    {
        return const_reverse_iterator(end());
    }
    const const_reverse_iterator rend() const
    {
        return const_reverse_iterator(begin());
    }
    const const_reverse_iterator crend() const
    {
        return const_reverse_iterator(begin());
    }
    Xor_List(size_type count, const T& value = T(), const Allocator& alloc = Allocator()) : allocator(alloc), size_list(count)
    {
        it_end = nullptr;
        it_begin = nullptr;
        for (size_type i = 0; i < count; i++)
        {
            push_back(value);
        }
    }
    Xor_List(const Xor_List& other)
    {
        allocator = other.allocator;
        it_begin = other.it_begin;
        it_end = other.it_end;
        size = other.size;
    }
    Xor_List(const Xor_List&& other)
    {
        allocator = std::move(other.allocator);
        it_begin = std::move(other.it_begin);
        it_end = std::move(other.it_end);
        size = std::move(other.size);
    }
    ~Xor_List()
    {
        for (size_type i = 0; i < size_list; i++)
        {
            erase(begin);
        }
    }
    node<T>* create_new_node(T value, node<T>* prev_value = nullptr, node<T>* next_value = nullptr)
    {
        return placement_new(allocator->allocate(1), node<T>(value, prev_value, next_value));
    }
    void delete_node(node<T>* current_node)
    {
        placement_delete(current_node);
        allocator->deallocate(current_node);
    }
    Xor_List& operator=(const Xor_List& other)
    {
        allocator = other.allocator;
        it_begin = other.it_begin;
        it_end = other.it_end;
        size = other.size;
        return (*this);
    }
    Xor_List&& operator=(const Xor_List&& other)
    {
        allocator = std::move(other.allocator);
        it_begin = std::move(other.it_begin);
        it_end = std::move(other.it_end);
        size = std::move(other.size);
        return (*this);
    }
    size_type size()
    {
        return size_list;
    }
    void push_back(const T& value)
    {
        insert_after(--end(), value);
    }
    void push_back(T&& value)
    {
        insert_after(--end(), value);
    }
    void push_front(const T& value)
    {
        insert_before(begin(), value);
    }
    void push_front(T&& value)
    {
        insert_before(begin(), value);
    }
    void pop_back()
    {
        erase(--end());
    }
    void pop_front()
    {
        erase(begin());
    }
    void insert_before(iterator it, const T& value)
    {
        if (it == nullptr)
        {
            node<T>* current = create_new_node(value, nullptr, nullptr);
            it_begin = current;
            it_end = current;
            size_list++;
            return;
        }
        iterator it1 = --it;
        it++;
        node<T>* prev = *it1;
        node<T>* next = *it;
        node<T>* current = create_new_node(value, prev, next);
        prev->update(current);
        next->update(current);
        if (it_begin == next)
        {
            it_begin = current;
        }
        size_list++;
    }
    void insert_before(iterator it, T&& value)
    {
        if (it == nullptr)
        {
            node<T>* current = create_new_node(std::move(value), nullptr, nullptr);
            it_begin = current;
            it_end = current;
            size_list++;
            return;
        }
        iterator it1 = --it;
        it++;
        node<T>* prev = *it1;
        node<T>* next = *it;
        node<T>* current = create_new_node(std::move(value), prev, next);
        prev->update(current);
        next->update(current);
        if (it_begin == next)
        {
            it_begin = current;
        }
        size_list++;
    }
    void insert_after(iterator it, const T& value)
    {
        if (it == nullptr)
        {
            node<T>* current = create_new_node(value, nullptr, nullptr);
            it_begin = current;
            it_end = current;
            size_list++;
            return;
        }
        iterator it1 = ++it;
        it--;
        node<T>* next = *it1;
        node<T>* prev = *it;
        node<T>* current = create_new_node(value, prev, next);
        prev->update(current);
        next->update(current);
        if (it_end == prev)
        {
            it_end = current;
        }
        size_list++;
    }
    void insert_after(iterator it, T&& value)
    {
        if (it == nullptr)
        {
            node<T>* current = create_new_node(std::move(value), nullptr, nullptr);
            it_begin = current;
            it_end = current;
            size_list++;
            return;
        }
        iterator it1 = ++it;
        it--;
        node<T>* next = *it1;
        node<T>* prev = *it;
        node<T>* current = create_new_node(std::move(value), prev, next);
        prev->update(current);
        next->update(current);
        if (it_end == prev)
        {
            it_end = current;
        }
        size_list++;
    }
    void erase(iterator it)
    {
        node<T>* prev = *(--it);
        it++;
        node<T>* next = *(++it);
        node<T>* current = *(--it);
        node<T>* prev1 = prev;
        prev.update(current);
        prev.update(next);
        next.update(current);
        next.update(prev1);
        size_list--;
        if (it == it_begin)
        {
            it_begin = next;
        }
        if (it == it_end)
        {
            it_end = prev;
        }
        delete_node(current);
    }
};

 int main()
 {
//     Stack_Allocator<int> allocator;
//     allocator.allocate(10000);
//     std::list<int, Stack_Allocator<int>> list1;
//     //for (int i = 1; i <= 600000; i++)
//     //{
//     //  list1.push_back(5);
//     //}
     return 0;
 }