#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

template <typename T>
class Deque {
private:
    deque<T> data;

public:
    void insertFront(const T& e) {
        data.push_front(e);
    }

    void insertBack(const T& e) {
        data.push_back(e);
    }

    void eraseFront() {
        if (!data.empty()) {
            data.pop_front();
        }
    }
    void eraseBack() {
        if (!data.empty()) {
            data.pop_back();
        }
    }

    T front() const {
        if (!data.empty()) {
            return data.front();
        }
        throw out_of_range("Deque is empty");
    }

    T back() const {
        if (!data.empty()) {
            return data.back();
        }
        throw out_of_range("Deque is empty");
    }

    size_t size() const {
        return data.size();
    }

    bool empty() const {
        return data.empty();
    }

    const deque<T>& getData() const {
        return data;
    }
};

template <typename T>
Deque<T> mergeSortedDeques(const Deque<T>& d1, const Deque<T>& d2) {
    Deque<T> result;
    deque<T> temp1 = d1.getData();
    deque<T> temp2 = d2.getData();

    // Сливане в нарастващ ред
    while (!temp1.empty() && !temp2.empty()) {
        if (temp1.front() < temp2.front()) {
            result.insertBack(temp1.front());
            temp1.pop_front();
        } else {
            result.insertBack(temp2.front());
            temp2.pop_front();
        }
    }

    while (!temp1.empty()) {
        result.insertBack(temp1.front());
        temp1.pop_front();
    }

    while (!temp2.empty()) {
        result.insertBack(temp2.front());
        temp2.pop_front();
    }

    return result;
}

int main() {
    Deque<int> d1, d2;

    int n1, n2, value;

    cout << "Enter the number of elements for the first deque: ";
    cin >> n1;
    cout << "Enter the elements for the first deque in sorted order: " << endl;
    for (int i = 0; i < n1; ++i) {
        cin >> value;
        d1.insertBack(value);
    }

    cout << "Enter the number of elements for the second deque: ";
    cin >> n2;
    cout << "Enter the elements for the second deque in sorted order: " << endl;
    for (int i = 0; i < n2; ++i) {
        cin >> value;
        d2.insertBack(value);
    }

    // Сливане на двата дека
    Deque<int> result = mergeSortedDeques(d1, d2);

    cout << "Merged deque: ";
    while (!result.empty()) {
        cout << result.front() << " ";
        result.eraseFront();
    }
    cout << endl;

    return 0;
}