#include <iostream>
#include <string>
#include <fstream>

using namespace std;

struct Node {
    int data;
    Node* next;
};

int inputValue(int min, int max);
pair<int, int> userInputFromConsole();
pair<int, int> userInputFromFile(string path);
bool checkPath(string path);
string userInputPath();
short inputMethod();
void printInConsole(string ans);
string userOutputPath();
void printInFile(string ans, string path);
short outputMethod();
void start();
void printTask();

int inputValue(int min, int max) {
    int currentValue;
    bool isNotValid = true;
    do {
        cin >> currentValue;
        if (currentValue >= min && currentValue <= max)
            isNotValid = false;
        else
            cout << "Введите число в заданном диапазоне\n";
    } while (isNotValid);
    return currentValue;
}

pair<int, int> userInputFromConsole() {
    const int MIN_SIZE = 1;
    const int MAX_SIZE = 20;
    int n, m;
    cout << "Введите N и M в диапазоне " << MIN_SIZE << ".." << MAX_SIZE << ": ";
    n = inputValue(MIN_SIZE, MAX_SIZE);
    m = inputValue(MIN_SIZE, MAX_SIZE);
    return make_pair(n, m);
}

pair<int, int> userInputFromFile(string path) {
    int n, m;
    ifstream file(path);
    file.open(path);
    file.clear();
    file >> n;
    file >> m;
    file.close();
    return make_pair(n, m);
}

bool checkPath(string path) {
    ifstream file(path);
    if (file.is_open()) {
        cout << path << " найден" << endl;
        return true;
    }
    else {
        cout << path << " не найден" << endl;
        return false;
    }
}

string userInputPath() {
    string path;
    bool isNotValid = false;
    do {
        cout << "Введите абсолютный путь к файлу с входными данными" << endl;
        cin >> path;
    } while (!checkPath(path));
    return path;
}

short inputMethod() {
    short method;
    cout << "Каким способом хотите ввести данные?" << endl;
    cout << "1 - с помощью консоли" << endl;
    cout << "2 - с помощью файла" << endl;
    do {
        cin >> method;
        if (method != 1 && method != 2)
            cout << "Введите 1 или 2" << endl;
    } while (method != 2 && method != 1);
    return method;
}

void printInConsole(string ans) {
    cout << ans;
}

string userOutputPath() {
    string path;
    cout << "Введите абсолютный путь к файлу для вывода результата" << endl;
    cin >> path;
    return path;
}

void printInFile(string ans, string path) {
    ofstream file(path);
    file << ans;
    cout << "Результат работы помещён в файл";
}

short outputMethod() {
    short method;
    cout << "Куда хотите вывести результат?" << endl;
    cout << "1 - в консоль" << endl;
    cout << "2 - в файл" << endl;
    do {
        cin >> method;
        if (method != 1 && method != 2)
            cout << "Введите 1 или 2" << endl;
    } while (method != 2 && method != 1);
    return method;
}

pair<int, int> userInput() {
    pair<int, int> size;
    short method = inputMethod();
    if (method == 1) {
        size = userInputFromConsole();
    }
    else {
        string path = userInputPath();
        size = userInputFromFile(path);
    }
    return size;
}

void printResult(string ans) {
    short method = outputMethod();
    if (method == 1)
        printInConsole(ans);
    else {
        string path = userOutputPath();
        printInFile(ans, path);
    }
}

Node* add(Node *head, Node *list, int info) {
    Node* addList = (Node*)malloc(sizeof(Node));
    addList->data = info;
    addList->next = NULL;
    if (head == NULL) {
        head = addList;
        list = addList;
    }
    else {
        list = head;
        while (list->next != NULL)
            list = list->next;
        list->next = addList;
    }
    return head;
}

Node* deleteList(Node* list, Node* head) {
    Node* temp = head;
    while (temp->next != list)
        temp = temp->next;
    temp->next = temp->next->next;
    return temp->next;
}

Node* createList(int n) {
    Node* list = NULL;
    Node* head = NULL;
    for (int i = 0; i < n; i++) {
        list = add(list, list, i + 1);
    }
    head = list;
    while (list->next != NULL)
        list = list->next;
    list->next = head;
    list = head;
    return list;
}

void printTask() {
    cout << "N ребят встали в круг. Каждый раз, начиная с первого, из круга выводится каждый M-й. Вывести номера в порядке выбывания и номер последнего оставшегося." << endl;
}

void start() {
    printTask();
    pair<int, int> size = userInput();
    int n = size.first;
    int m = size.second;
    Node* list = createList(n);
    Node* head = list;
    int now = 0;
    string ans = "Номера в порядке выбывания: \n";
    while (n > 1) {
        now++;
        if (now == m) {
            ans += to_string(list->data) + " ";
            list = deleteList(list, head);
            head = list;
            now = 0;
            n--;
        }
        else
            list = list->next;
    }
    ans += "\nНомер последнего оставшегося: " + to_string(list->data);
    printResult(ans);
}

int main()
{
    setlocale(LC_ALL, "Russian");
    start();
}