#include <bits/stdc++.h>

using namespace std;

/*
Be:
10 14
3 10
1 7
3 1
10 12
3 9
4 5
6 6
8 10
10 13
3 7



*/
typedef struct {
   int eleje, vege, sorszam;
}Tartam;



bool sorrend (Tartam egyik, Tartam masik )
{
    return (egyik.vege<masik.vege);
}

int main()
{
    int n, napok;
    cin>>n;  //megrendelesek
    cin>>napok; //a napok szama

    vector<Tartam> intervallum;
    Tartam uj;
    for(int i=1;i<=n;i++)
    {
        cin>> uj.eleje>>uj.vege;
        uj.sorszam=i;
        intervallum.push_back(uj);
    }
    cout<<endl;
    for (Tartam x:intervallum)
        cout<<x.eleje<<" "<<x.vege<<endl;

    sort(intervallum.begin(),intervallum.end(),sorrend);

    cout<<endl;
    for (Tartam x:intervallum)
        cout<<x.eleje<<" "<<x.vege<<" "<<x.sorszam<< endl;

    vector <Tartam> mester;
    vector <Tartam> fia;
    int autolso=0, futolso=0;
    int i=0;
    int fszam=0, aszam=0;
    while (i<n)
    {
       Tartam x=intervallum.at(i);
       if (x.eleje>autolso)
       {
           mester.push_back(x);
           autolso=x.vege;
           aszam++;
       }
       else if (x.eleje>futolso)
       {
           fia.push_back(x);
           futolso=x.vege;
           fszam++;
       }
       i++;
    }
    cout<<aszam<<" "<<fszam<<endl;
        
    for(Tartam x:mester)
        cout << "mester\t" <<x.eleje<<" "<<x.vege<<" "<<x.sorszam<< endl;
    for(Tartam x:fia)
        cout << "fia\t" <<x.eleje<<" "<<x.vege<<" "<<x.sorszam<< endl;
    return 0;
}