alg2

#include<algorithm>
#include <iostream>
#include <string>
#include<cmath>



struct Osoba {
public:
    std::string nazwisko;
    long int minutes = 0;



};

int main()
{
 std::ios::sync_with_stdio(false);

    long int t = 0; //liczba zestawóów danych
    long int n = 0; //liczba nazwisk
    long int p = 0; //liczba nazwisk któe trzeba wyświetlić

    std::cin >> t;

    //wczytywanie
    for (long int i = 0; i < t; i++) {




        std::cin >> n;  //***PROCEDURA WCZYTYWANIA DANYCH POCZĄTKOWYCH***
        std::cin >> p;

        if (p > n)break;

        Osoba* nowy = new Osoba[n];
        //wczytywanie nazwisk i czasów
        for (long int q = 0; q < n; q++) {
            std::cin >> nowy[q].nazwisko >> nowy[q].minutes;

        }
        long int wynik = 0;
        long int zgodzilisie = 0;//ile osob sie zgodzilo


            //sortowanie wybieranie
        Osoba tmp_minutes;
        Osoba tmp_nazwisko;
        for (long int i = 1; i < n; i++) {

            if (nowy[i - 1].minutes > nowy[i].minutes)
                tmp_minutes = nowy[i];                                          //wybieram sobie mniejszy element tablicy i zapisuję go do zmiennej tymczasowej żeby sobie go potem móc podmienić w odpowienim miejscu
            for (long int j = i - 1; j >= 0 && nowy[j].minutes > tmp_minutes.minutes; j--) {//ta pętla zapewnia mi, że mniejszy element zostanie wciśnięty w odpowiednie miejsce

                if (nowy[j].minutes == nowy[j+1].minutes && nowy[j].nazwisko < nowy[j+1].nazwisko)std::swap(nowy[j], nowy[j+1]);
                if (nowy[j].minutes > nowy[j + 1].minutes) {
                    tmp_minutes = nowy[j + 1];
                    nowy[j + 1] = nowy[j];                                          //tutaj robię podmianę żeby kolejnośc była wg liczby minut
                    nowy[j] = tmp_minutes;



                    if (nowy[j].minutes == nowy[j - 1].minutes && nowy[j].nazwisko > nowy[j - 1].nazwisko) {

                        std::swap(nowy[j], nowy[j - 1]);
                    }


                }

            }




        }
        //if (nowy[n - 1].minutes == nowy[n - 2].minutes && nowy[n - 1].nazwisko > nowy[n - 2].nazwisko)std::swap(nowy[n-1], nowy[n - 2]);

        //wypisanie odpowiedniej ilosci nazwisk

        for (long int i = n - 1; i >= n - p; i--) {

            std::cout << nowy[i].nazwisko << " ";


        }
        //wypisanie wyniku i eluwa
        for (long int i = n - 1; i >= 0; i--) {

            wynik += 1 + (nowy[i].minutes * zgodzilisie);

            zgodzilisie++;
        }

        std::cout << std::endl << wynik%1000003 << std::endl;


        delete[] nowy;


    }


    return 0;
}

//*******************WYCIETE KODY*********************

//-----------------sortowanie jeśli pierwsza litera jest pozniej w alfabecie to jest podmianka-------------------
                //if (nowy[j].minutes == nowy[j - 1].minutes && nowy[j].nazwisko < nowy[j - 1].nazwisko) {
            //
                //  std::swap(nowy[j], nowy[j - 1]);
                //}//----------------------tutaj sobie rypirympi jeśli litery są takie same wtedy przeglądam kolejno litery nazwiska i szukam wcześniejszej. wtedy dokonuje zamiany i przrywam pętlę
                //long int dl = nowy[j].nazwisko.length();
                //if (nowy[j].minutes == nowy[j - 1].minutes && nowy[j].nazwisko[0] == nowy[j - 1].nazwisko[0]) {
                //  for (long int literka = 0; literka < dl; literka++) {
                //      if (nowy[j].nazwisko[literka] < nowy[j - 1].nazwisko[literka]) {
                //          std::swap(nowy[j], nowy[j - 1]);
                //
                //      break;
                //      }
                //  }
                //
                //}
                //