#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector<vector<int>> save(int n, int k) {
    vector<vector<int>> save; // Vector để lưu trữ các vector con
    vector<vector<int>> done; 

    // Thêm từng chỉ số từ 1 đến n vào save như một vector con
    for (int i = 1; i <= n; i++) {
        vector<int> temp; // Tạo một vector tạm
        temp.push_back(i); // Thêm chỉ số i vào vector tạm
        save.push_back(temp); // Thêm vector tạm vào save
    }
    
    while (!save.empty()) {
        vector<int> A = save.back(); // Lấy vector con cuối cùng
        save.pop_back(); // Xóa vector đó khỏi save
        int a = A.back(); // Lấy phần tử cuối cùng của vector A
        int gap = k; // Bắt đầu với độ giãn là k
        
        while (true) {
            // Kiểm tra vị trí hợp lệ
            if (a + gap <= n) {
                vector<int> x = A; // Sao chép A vào x
                x.push_back(a + gap); // Thêm chỉ số hợp lệ vào x
                save.push_back(x); // Thêm x vào save
            } else {
                done.push_back(A); // Thêm A vào done
                break; // Thoát khỏi vòng lặp
            }
            gap++; // Tăng độ giãn lên 1
        }
    }
    
    return done; // Trả về các vector con đã tìm thấy
}

int main() {
    int n, k;
    
    cout << "Nhap n: ";
    cin >> n; // Nhập vào n
    
    cout << "Nhap k: ";
    cin >> k; // Nhập vào k

    vector<vector<int>> result = save(n, k);

    // Đếm số lần xuất hiện của từng phần tử trong result
    unordered_map<int, int> countMap; // Sử dụng unordered_map để đếm số lần xuất hiện

    cout << "Cac vector trong done:" << endl; // In ra các vector trong done
    for (const auto& vec : result) {
        for (int num : vec) {
            countMap[num]++; // Tăng số lần xuất hiện của phần tử num
        }
        // In ra từng vector
        cout << "{ ";
        for (int num : vec) {
            cout << num << " ";
        }
        cout << "}" << endl; // Xuống dòng
    }

    // Tính tổng
    int totalSum = 0;
    for (const auto& pair : countMap) {
        totalSum += pair.first * pair.second; // Tính tổng theo yêu cầu
        // In ra số lần xuất hiện của từng phần tử
        cout << "Phan tu " << pair.first << " xuat hien " << pair.second << " lan." << endl;
    }

    cout << "Tong cac phan tu xuat hien trong save: " << totalSum << endl; // In ra tổng

    return 0;
}