#include <iostream>

using namespace std;

struct Node1 {
    int data;
    Node1* prev;
    Node1* next;
} * START1;

struct Node2 {
    int data;
    Node2* prev;
    Node2* next;
}* START2 = NULL;

struct Node3 {
    int data;
    Node3* prev;
    Node3* next;
}* START3 ;



Node1* createNode1(int data) {
    Node1* newNode = new Node1;
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

Node2* createNode2(int data) {
    Node2* newNode = new Node2;
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

Node3* createNode3(int data) {
    Node3* newNode = new Node3;
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

void appendNode1(Node1*& head, int data) {
    Node1* newNode = createNode1(data);
    if (head == NULL) {
        head = newNode;
    }
    else {
        Node1* temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}

void appendNode2(Node2*& head, int data) {
    Node2* newNode = createNode2(data);
    if (head == NULL) {
        head = newNode;
    }
    else {
        Node2* temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}

void appendNode3(Node3*& head, int data) {
    Node3* newNode = createNode3(data);
    if (head == NULL) {
        head = newNode;
    }
    else {
        Node3* temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}

void deleteNode1(Node1*& head, int data) {
    Node1* temp = head;
    while (temp != NULL && temp->data != data) {
        temp = temp->next;
    }
    if (temp != NULL) {
        if (temp->prev != NULL) {
            temp->prev->next = temp->next;
        }
        else {
            head = temp->next;
        }
        if (temp->next != NULL) {
            temp->next->prev = temp->prev;
        }
        delete temp;
    }
}

void deleteNode2(Node2*& head, int data) {
    Node2* temp = head;
    while (temp != NULL && temp->data != data) {
        temp = temp->next;
    }
    if (temp != NULL) {
        if (temp->prev != NULL) {
            temp->prev->next = temp->next;
        }
        else {
            head = temp->next;
        }
        if (temp->next != NULL) {
            temp->next->prev = temp->prev;
        }
        delete temp;
    }
}

void printList1(Node1* head) {
    Node1* temp = head;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

void printList2(Node2* head) {
    Node2* temp = head;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

void printList3(Node3* head) {
    Node3* temp = head;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

Node3* mergeSortedLists(Node1* start1, Node2* start2) {
    Node3* result = NULL;

    Node1* temp1 = start1;
    Node2* temp2 = start2;

    while (temp1 != NULL && temp2 != NULL) {
        if (temp1->data <= temp2->data) {
            appendNode3(result, temp1->data);
            temp1 = temp1->next;
        }
        else {
            appendNode3(result, temp2->data);
            temp2 = temp2->next;
        }
    }

    while (temp1 != NULL) {
        appendNode3(result, temp1->data);
        temp1 = temp1->next;
    }

    while (temp2 != NULL) {
        appendNode3(result, temp2->data);
        temp2 = temp2->next;
    }

    return result;
}

void menu() {
    int choice, data;

    do {
        cout << "1. Add to List 1\n";
        cout << "2. Add to List 2\n";
        cout << "3. Delete from List 1\n";
        cout << "4. Delete from List 2\n";
        cout << "5. Print List 1\n";
        cout << "6. Print List 2\n";
        cout << "7. Merge Lists\n";
        cout << "8. Print Merged List\n";
        cout << "9. Exit\n";
        cout << "Enter your choice: ";
        cin >> choice;

        switch (choice) {
        case 1:
            cout << "Enter data to add to List 1: ";
            cin >> data;
            appendNode1(START1, data);
            break;
        case 2:
            cout << "Enter data to add to List 2: ";
            cin >> data;
            appendNode2(START2, data);
            break;
        case 3:
            cout << "Enter data to delete from List 1: ";
            cin >> data;
            deleteNode1(START1, data);
            break;
        case 4:
            cout << "Enter data to delete from List 2: ";
            cin >> data;
            deleteNode2(START2, data);
            break;
        case 5:
            cout << "List 1: ";
            printList1(START1);
            break;
        case 6:
            cout << "List 2: ";
            printList2(START2);
            break;
        case 7:
            START3 = mergeSortedLists(START1, START2);
            cout << "Lists merged.\n";
            break;
        case 8:
            cout << "Merged List: ";
            printList3(START3);
            break;
        case 9:
            cout << "Exiting.\n";
            break;
        default:
            cout << "Invalid choice. Please try again.\n";
        }
    } while (choice != 9);
}

int main() {
    menu();
    return 0;
}