#include <iostream>
#include <vector>

using namespace std;

void printRod(vector<int>& rod) {
    for (int disk : rod) {
        cout << disk << " ";
    }
    cout << endl;
}

void moveDisks(int n, vector<int>& source, vector<int>& target, vector<int>& auxiliary, char s, char t, char a) {
    if (n > 0) {
        moveDisks(n - 1, source, auxiliary, target, s, a, t);
        target.push_back(source.back());
        source.pop_back();

        cout << "Move disk " << n << " from " << s << " to " << t << endl;
        cout << "A: "; printRod(source);
        cout << "B: "; printRod(auxiliary);
        cout << "C: "; printRod(target);
        cout << endl;

        moveDisks(n - 1, auxiliary, target, source, a, t, s);
    }
}

int main() {
    int n;  // Number of disks
    cout << "Enter the number of disks: ";
    cin >> n;

    vector<int> A, B, C;
    // Initialize the source rod with disks 1 to n, where 1 is the smallest disk
    for (int i = n; i > 0; i--) {
        A.push_back(i);
    }

    cout << "Initial state:\n";
    cout << "A: "; printRod(A);
    cout << "B: "; printRod(B);
    cout << "C: "; printRod(C