---

#include <iostream>
#include <stdexcept>
#include <algorithm>
#include <cstddef>

using namespace std;

// ===============================
// Общий узел для двусвязных списков
// ===============================
template <typename T>
struct DoubleNode {
    T data;
    DoubleNode* prev;
    DoubleNode* next;
    DoubleNode(const T& val) : data(val), prev(nullptr), next(nullptr) {}
};

// ===============================
// Вспомогательные функции сортировки слиянием
// ===============================
template <typename T>
DoubleNode<T>* mergeSorted(DoubleNode<T>* a, DoubleNode<T>* b) {
    if (!a) return b;
    if (!b) return a;

    DoubleNode<T>* head = nullptr;
    DoubleNode<T>* tail = nullptr;

    while (a && b) {
        if (a->data <= b->data) {
            if (!head) {
                head = tail = a;
            }
            else {
                tail->next = a;
                a->prev = tail;
                tail = a;
            }
            a = a->next;
        }
        else {
            if (!head) {
                head = tail = b;
            }
            else {
                tail->next = b;
                b->prev = tail;
                tail = b;
            }
            b = b->next;
        }
    }

    if (a) {
        tail->next = a;
        a->prev = tail;
    }
    else if (b) {
        tail->next = b;
        b->prev = tail;
    }

    // Обнуляем next у последнего узла
    DoubleNode<T>* cur = head;
    while (cur->next) cur = cur->next;
    cur->next = nullptr;

    if (head) head->prev = nullptr;
    return head;
}

template <typename T>
DoubleNode<T>* mergeSort(DoubleNode<T>* head) {
    if (!head || !head->next) return head;

    // Разделение списка пополам (быстрый и медленный указатели)
    DoubleNode<T>* slow = head;
    DoubleNode<T>* fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    DoubleNode<T>* mid = slow->next;
    slow->next = nullptr;
    if (mid) mid->prev = nullptr;

    DoubleNode<T>* left = mergeSort(head);
    DoubleNode<T>* right = mergeSort(mid);

    return mergeSorted(left, right);
}

// ===============================
// Задание 1.1. Шаблонный двусвязный список
// ===============================
template <typename T>
class DoubleList {
private:
    DoubleNode<T>* head;
    DoubleNode<T>* tail;
    size_t sz;

    void copyFrom(const DoubleList& other) {
        for (DoubleNode<T>* cur = other.head; cur; cur = cur->next) {
            push_back(cur->data);
        }
    }

public:
    class iterator {
        DoubleNode<T>* node;
        DoubleList<T>* owner;
        size_t index;

    public:
        iterator(DoubleNode<T>* n = nullptr, DoubleList<T>* o = nullptr, size_t i = 0)
            : node(n), owner(o), index(i) {
        }

        T& operator*() const {
            if (!node) throw out_of_range("dereference of end iterator");
            return node->data;
        }

        T* operator->() const {
            return &node->data;
        }

        iterator& operator++() {
            if (!owner || index >= owner->sz)
                throw out_of_range("++ on end iterator");
            node = node->next;
            ++index;
            return *this;
        }

        iterator operator++(int) {
            iterator tmp = *this;
            ++(*this);
            return tmp;
        }

        iterator& operator--() {
            if (!owner) throw out_of_range("-- on invalid iterator");
            if (node == nullptr) {
                if (owner->sz == 0)
                    throw out_of_range("-- on empty DoubleList");
                node = owner->tail;
                index = owner->sz - 1;
            }
            else {
                node = node->prev;
                --index;
            }
            return *this;
        }

        iterator operator--(int) {
            iterator tmp = *this;
            --(*this);
            return tmp;
        }

        bool operator==(const iterator& other) const {
            return owner == other.owner && index == other.index;
        }

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

        friend class DoubleList;
    };

    DoubleList() : head(nullptr), tail(nullptr), sz(0) {}

    ~DoubleList() {
        clear();
    }

    DoubleList(const DoubleList& other) : head(nullptr), tail(nullptr), sz(0) {
        copyFrom(other);
    }

    DoubleList(DoubleList&& other) noexcept
        : head(other.head), tail(other.tail), sz(other.sz) {
        other.head = other.tail = nullptr;
        other.sz = 0;
    }

    DoubleList& operator=(const DoubleList& other) {
        if (this != &other) {
            clear();
            copyFrom(other);
        }
        return *this;
    }

    DoubleList& operator=(DoubleList&& other) noexcept {
        if (this != &other) {
            clear();
            head = other.head;
            tail = other.tail;
            sz = other.sz;
            other.head = other.tail = nullptr;
            other.sz = 0;
        }
        return *this;
    }

    void push_front(const T& val) {
        DoubleNode<T>* node = new DoubleNode<T>(val);
        if (!head) {
            head = tail = node;
        }
        else {
            node->next = head;
            head->prev = node;
            head = node;
        }
        ++sz;
    }

    void push_back(const T& val) {
        DoubleNode<T>* node = new DoubleNode<T>(val);
        if (!head) {
            head = tail = node;
        }
        else {
            tail->next = node;
            node->prev = tail;
            tail = node;
        }
        ++sz;
    }

    void pop_front() {
        if (empty()) throw out_of_range("pop_front from empty DoubleList");
        DoubleNode<T>* tmp = head;
        head = head->next;
        if (head) head->prev = nullptr;
        else tail = nullptr;
        delete tmp;
        --sz;
    }

    void pop_back() {
        if (empty()) throw out_of_range("pop_back from empty DoubleList");
        DoubleNode<T>* tmp = tail;
        tail = tail->prev;
        if (tail) tail->next = nullptr;
        else head = nullptr;
        delete tmp;
        --sz;
    }

    iterator insert(iterator pos, const T& val) {
        if (pos.owner != this)
            throw invalid_argument("iterator from another DoubleList");

        if (pos.node == nullptr) { // вставка в конец
            push_back(val);
            return iterator(tail, this, sz - 1);
        }

        DoubleNode<T>* cur = pos.node;
        DoubleNode<T>* node = new DoubleNode<T>(val);
        node->next = cur;
        node->prev = cur->prev;

        if (cur->prev) cur->prev->next = node;
        else head = node;

        cur->prev = node;
        ++sz;
        return iterator(node, this, pos.index);
    }

    iterator erase(iterator pos) {
        if (pos.owner != this)
            throw invalid_argument("iterator from another DoubleList");
        if (pos.node == nullptr)
            throw out_of_range("erase on end iterator");

        DoubleNode<T>* cur = pos.node;
        DoubleNode<T>* next = cur->next;
        DoubleNode<T>* prev = cur->prev;

        if (prev) prev->next = next;
        else head = next;

        if (next) next->prev = prev;
        else tail = prev;

        delete cur;
        --sz;
        return iterator(next, this, pos.index);
    }

    void clear() {
        DoubleNode<T>* cur = head;
        while (cur) {
            DoubleNode<T>* next = cur->next;
            delete cur;
            cur = next;
        }
        head = tail = nullptr;
        sz = 0;
    }

    size_t size() const { return sz; }
    bool empty() const { return sz == 0; }

    iterator begin() { return iterator(head, this, 0); }
    iterator end() { return iterator(nullptr, this, sz); }

    // Задание 2.1. Разворот списка
    void reverse() {
        if (sz < 2) return;
        DoubleNode<T>* cur = head;
        while (cur) {
            swap(cur->next, cur->prev);
            cur = cur->prev; // после swap prev — это бывший next
        }
        swap(head, tail);
    }

    // Задание 2.2. Слияние двух отсортированных списков
    void merge(DoubleList& other) {
        if (this == &other) return;

        DoubleNode<T>* a = head;
        DoubleNode<T>* b = other.head;

        head = tail = nullptr;
        size_t newSz = 0;

        while (a && b) {
            if (a->data <= b->data) {
                DoubleNode<T>* next = a->next;
                a->prev = tail;
                if (tail) tail->next = a;
                else head = a;
                tail = a;
                a = next;
            }
            else {
                DoubleNode<T>* next = b->next;
                b->prev = tail;
                if (tail) tail->next = b;
                else head = b;
                tail = b;
                b = next;
            }
            ++newSz;
        }

        while (a) {
            DoubleNode<T>* next = a->next;
            a->prev = tail;
            if (tail) tail->next = a;
            else head = a;
            tail = a;
            a = next;
            ++newSz;
        }

        while (b) {
            DoubleNode<T>* next = b->next;
            b->prev = tail;
            if (tail) tail->next = b;
            else head = b;
            tail = b;
            b = next;
            ++newSz;
        }

        if (head) head->prev = nullptr;
        if (tail) tail->next = nullptr;
        sz = newSz;

        other.head = other.tail = nullptr;
        other.sz = 0;
    }

    // Задание 2.3. Сортировка слиянием (без массива)
    void sort() {
        if (sz < 2) return;
        head = mergeSort(head);
        tail = head;
        while (tail->next) tail = tail->next;
        if (head) head->prev = nullptr;
        if (tail) tail->next = nullptr;
    }
};

// ===============================
// Задание 1.2. Кольцевой двусвязный список
// ===============================
template <typename T>
class RingDoubleList {
private:
    DoubleNode<T>* head;
    DoubleNode<T>* tail;
    size_t sz;

    void copyFrom(const RingDoubleList& other) {
        if (other.empty()) return;
        DoubleNode<T>* cur = other.head;
        for (size_t i = 0; i < other.sz; ++i) {
            push_back(cur->data);
            cur = cur->next;
        }
    }

public:
    class iterator {
        DoubleNode<T>* node;
        RingDoubleList<T>* owner;
        size_t index;

    public:
        iterator(DoubleNode<T>* n = nullptr, RingDoubleList<T>* o = nullptr, size_t i = 0)
            : node(n), owner(o), index(i) {
        }

        T& operator*() const {
            if (!node || index >= owner->sz)
                throw out_of_range("dereference of end iterator");
            return node->data;
        }

        T* operator->() const {
            return &node->data;
        }

        iterator& operator++() {
            if (!owner || index >= owner->sz)
                throw out_of_range("++ on end iterator");
            ++index;
            node = node->next;
            return *this;
        }

        iterator operator++(int) {
            iterator tmp = *this;
            ++(*this);
            return tmp;
        }

        iterator& operator--() {
            if (!owner) throw out_of_range("-- on invalid iterator");
            if (index == owner->sz) { // end
                if (owner->sz == 0)
                    throw out_of_range("-- on empty ring");
                index = owner->sz - 1;
                node = owner->tail;
            }
            else {
                --index;
                node = node->prev;
            }
            return *this;
        }

        iterator operator--(int) {
            iterator tmp = *this;
            --(*this);
            return tmp;
        }

        bool operator==(const iterator& other) const {
            return owner == other.owner && index == other.index;
        }

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

        friend class RingDoubleList;
    };

    RingDoubleList() : head(nullptr), tail(nullptr), sz(0) {}

    ~RingDoubleList() {
        clear();
    }

    RingDoubleList(const RingDoubleList& other) : head(nullptr), tail(nullptr), sz(0) {
        copyFrom(other);
    }

    RingDoubleList(RingDoubleList&& other) noexcept
        : head(other.head), tail(other.tail), sz(other.sz) {
        other.head = other.tail = nullptr;
        other.sz = 0;
    }

    RingDoubleList& operator=(const RingDoubleList& other) {
        if (this != &other) {
            clear();
            copyFrom(other);
        }
        return *this;
    }

    RingDoubleList& operator=(RingDoubleList&& other) noexcept {
        if (this != &other) {
            clear();
            head = other.head;
            tail = other.tail;
            sz = other.sz;
            other.head = other.tail = nullptr;
            other.sz = 0;
        }
        return *this;
    }

    void push_front(const T& val) {
        DoubleNode<T>* node = new DoubleNode<T>(val);
        if (empty()) {
            node->next = node;
            node->prev = node;
            head = tail = node;
        }
        else {
            node->next = head;
            node->prev = tail;
            head->prev = node;
            tail->next = node;
            head = node;
        }
        ++sz;
    }

    void push_back(const T& val) {
        DoubleNode<T>* node = new DoubleNode<T>(val);
        if (empty()) {
            node->next = node;
            node->prev = node;
            head = tail = node;
        }
        else {
            node->next = head;
            node->prev = tail;
            tail->next = node;
            head->prev = node;
            tail = node;
        }
        ++sz;
    }

    void pop_front() {
        if (empty()) throw out_of_range("pop_front from empty ring");
        if (sz == 1) {
            delete head;
            head = tail = nullptr;
            sz = 0;
            return;
        }
        DoubleNode<T>* tmp = head;
        head = head->next;
        head->prev = tail;
        tail->next = head;
        delete tmp;
        --sz;
    }

    void pop_back() {
        if (empty()) throw out_of_range("pop_back from empty ring");
        if (sz == 1) {
            delete head;
            head = tail = nullptr;
            sz = 0;
            return;
        }
        DoubleNode<T>* tmp = tail;
        tail = tail->prev;
        tail->next = head;
        head->prev = tail;
        delete tmp;
        --sz;
    }

    iterator insert(iterator pos, const T& val) {
        if (pos.owner != this)
            throw invalid_argument("iterator from another ring");

        if (empty()) {
            DoubleNode<T>* node = new DoubleNode<T>(val);
            node->next = node;
            node->prev = node;
            head = tail = node;
            sz = 1;
            return iterator(node, this, 0);
        }

        if (pos.index == sz) { // вставка в конец (перед end)
            push_back(val);
            return iterator(tail, this, sz - 1);
        }

        if (pos.index == 0) { // вставка перед head
            push_front(val);
            return iterator(head, this, 0);
        }

        DoubleNode<T>* cur = pos.node;
        DoubleNode<T>* node = new DoubleNode<T>(val);
        node->next = cur;
        node->prev = cur->prev;
        cur->prev->next = node;
        cur->prev = node;
        ++sz;
        return iterator(node, this, pos.index);
    }

    iterator erase(iterator pos) {
        if (pos.owner != this)
            throw invalid_argument("iterator from another ring");
        if (empty() || pos.index >= sz)
            throw out_of_range("erase invalid iterator");

        DoubleNode<T>* cur = pos.node;

        if (sz == 1) {
            delete cur;
            head = tail = nullptr;
            sz = 0;
            return end();
        }

        DoubleNode<T>* next = cur->next;
        DoubleNode<T>* prev = cur->prev;

        prev->next = next;
        next->prev = prev;

        if (cur == head) head = next;
        if (cur == tail) tail = prev;

        delete cur;
        --sz;

        if (pos.index == sz) { // удалили последний элемент
            return iterator(head, this, 0);
        }
        return iterator(next, this, pos.index);
    }

    void clear() {
        if (!head) return;
        DoubleNode<T>* cur = head;
        for (size_t i = 0; i < sz; ++i) {
            DoubleNode<T>* next = cur->next;
            delete cur;
            cur = next;
        }
        head = tail = nullptr;
        sz = 0;
    }

    size_t size() const { return sz; }
    bool empty() const { return sz == 0; }

    iterator begin() { return iterator(head, this, 0); }
    iterator end() { return iterator(head, this, sz); }

    // Поворот кольца на k позиций за O(min(k, n-k))
    void rotate(int k) {
        if (sz <= 1) return;
        k %= static_cast<int>(sz);
        if (k < 0) k += static_cast<int>(sz);
        if (k == 0) return;

        if (k <= static_cast<int>(sz) - k) {
            for (int i = 0; i < k; ++i) head = head->next;
            tail = head->prev;
        }
        else {
            int steps = static_cast<int>(sz) - k;
            for (int i = 0; i < steps; ++i) head = head->prev;
            tail = head->prev;
        }
    }

    // Эффективный поиск: идём с двух сторон навстречу
    iterator find(const T& value) {
        if (empty()) return end();

        DoubleNode<T>* f = head;
        DoubleNode<T>* b = tail;

        for (size_t i = 0; i <= sz / 2; ++i) {
            if (f->data == value) return iterator(f, this, i);
            if (b->data == value) return iterator(b, this, sz - 1 - i);

            f = f->next;
            b = b->prev;

            if (f == b) {
                if (f->data == value) return iterator(f, this, i + 1);
                break;
            }
        }
        return end();
    }

    // Задание 2.1. Разворот кольцевого списка
    void reverse() {
        if (sz < 2) return;
        DoubleNode<T>* cur = head;
        for (size_t i = 0; i < sz; ++i) {
            swap(cur->next, cur->prev);
            cur = cur->prev;
        }
        swap(head, tail);
    }

    // Задание 2.3. Сортировка кольцевого списка
    void sort() {
        if (sz < 2) return;

        // Разрываем кольцо
        head->prev = nullptr;
        tail->next = nullptr;

        head = mergeSort(head);

        // Находим новый хвост
        tail = head;
        while (tail->next) tail = tail->next;

        // Снова замыкаем в кольцо
        head->prev = tail;
        tail->next = head;
    }
};

// ===============================
// Задание 3.1. Проблема Иосифа
// ===============================
void josephus(int n, int k) {
    RingDoubleList<int> ring;
    for (int i = 1; i <= n; ++i) {
        ring.push_back(i);
    }

    cout << "========================================\n";
    cout << " Проблема Иосифа: n = " << n << ", k = " << k << "\n";
    cout << "========================================\n\n";

    auto it = ring.begin();
    int step = 0;

    // Ширина колонки для ровного вывода
    const int colWidth = 5;
    const int perRow = 10;

    cout << "Порядок удаления:\n";
    while (ring.size() > 1) {
        // Отсчитываем k-й элемент
        for (int i = 1; i < k; ++i) {
            ++it;
            if (it == ring.end()) it = ring.begin();
        }

        ++step;
        cout << "[" << step << "] " << *it << "  ";

        // Переход на новую строку каждые perRow элементов
        if (step % perRow == 0) cout << "\n";

        it = ring.erase(it);
        if (it == ring.end()) it = ring.begin();
    }

    if (step % perRow != 0) cout << "\n";
    cout << "\n";

    cout << "----------------------------------------\n";
    cout << " Всего удалено: " << step << "\n";
    cout << " Последний выживший: " << *ring.begin() << "\n";
    cout << "----------------------------------------\n";

    if (n == 41 && k == 3) {
        cout << " Проверка: ожидается 31 -> "
            << (*ring.begin() == 31 ? "OK" : "ОШИБКА") << "\n";
        cout << "----------------------------------------\n";
    }
}

// ===============================
// Демонстрация
// ===============================
int main() {
    setlocale(LC_ALL, "");

    cout << "===== Проверка DoubleList =====" << endl;

    DoubleList<int> lst;
    lst.push_back(3);
    lst.push_back(1);
    lst.push_back(2);
    lst.sort();

    cout << "Отсортированный DoubleList: ";
    for (auto it = lst.begin(); it != lst.end(); ++it)
        cout << *it << " ";
    cout << endl;

    DoubleList<int> a, b;
    a.push_back(1); a.push_back(3); a.push_back(5);
    b.push_back(2); b.push_back(4); b.push_back(6);

    a.merge(b);
    cout << "После merge: ";
    for (auto it = a.begin(); it != a.end(); ++it)
        cout << *it << " ";
    cout << endl;

    a.reverse();
    cout << "После reverse: ";
    for (auto it = a.begin(); it != a.end(); ++it)
        cout << *it << " ";
    cout << endl;

    cout << "\n===== Проверка RingDoubleList =====" << endl;

    RingDoubleList<int> ring;
    for (int i = 1; i <= 10; ++i) ring.push_back(i);

    cout << "Кольцо: ";
    auto rit = ring.begin();
    for (size_t i = 0; i < ring.size(); ++i) {
        cout << *rit << " ";
        ++rit;
    }
    cout << endl;

    ring.rotate(3);
    cout << "После rotate(3): ";
    rit = ring.begin();
    for (size_t i = 0; i < ring.size(); ++i) {
        cout << *rit << " ";
        ++rit;
    }
    cout << endl;

    ring.reverse();
    cout << "После reverse: ";
    rit = ring.begin();
    for (size_t i = 0; i < ring.size(); ++i) {
        cout << *rit << " ";
        ++rit;
    }
    cout << endl;

    cout << "\n===== Задание 3.1. Проблема Иосифа =====" << endl;
    josephus(41, 3); // Должен остаться элемент с начальной позицией 31

    return 0;
}