// UUID: 0b452b7f-8cec-4260-a8e8-a7d18abc647a
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, h;
    cin >> n >> h;
    vector<array<int,3>> munkak (n);
    for (int i = 0; i < n; i++) {
        cin >> munkak[i][1] >> munkak[i][0];
        munkak[i][2] = i+1;
    }
    sort(munkak.begin(),munkak.end());
    int foga = -1;
    int fogf = -1;
    vector<int> apa;
    vector<int> fia;
    int mh = 0;
    for (int i = 0; i < n; i++) {
        if (mh >= h) {
            break;
        }
        if (fogf < foga) {
            cout << "a";
            if (munkak[mh][1] > fogf) {
                fogf = munkak[mh][0];
                fia.push_back(munkak[mh][2]);
                cout << "a";
            }
            else if (munkak[mh][1] > foga) {
                foga = munkak[mh][0];
                apa.push_back(munkak[mh][2]);
                cout << "b";
            }
        }
        else {
            cout << "b";
            if (munkak[mh][1] > foga) {
                foga = munkak[mh][0];
                apa.push_back(munkak[mh][2]);
                cout << "a";
            }
            else if (munkak[mh][1] > fogf) {
                fogf = munkak[mh][0];
                fia.push_back(munkak[mh][2]);
                cout << "b";
            }
        }
        cout << "    ";
        mh++;
    }
    cout << apa.size() << " " << fia.size() << endl;
    for (int i = 0; i < apa.size(); i++) {
        cout << apa[i] << " ";
    }
    cout << endl;
    for (int i = 0; i < fia.size(); i++) {
        cout << fia[i] << " ";
    }
}