#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream f ("in.in");
ofstream g ("out.out");

typedef pair<int,int> Ipair;

struct Camera{
    int nrElevi,punctaj;
}seria1[10],seria2[10];

bool prim(int);
int cifControl(int);
void sol1();
void sol2();
void citire();

int main()
{
    citire();
    return 0;
}

bool prim(int x)
{
    if(x < 2 || x > 2 && x % 2 == 0)return 0;
    for(int i=3;i*i<=x;i+=2)
        if(x % i == 0)return 0;
    return 1;
}

int cifControl(int x)
{
    if(x == 0)return 0;
    if(x % 9 == 0)return 9;
    return x % 9;
}


void citire()
{
    int cerinta,n,x,punctaj,nr;
    f >> cerinta >> n;
    for(int i=1;i<=n;++i)
    {
        f >> x;
        punctaj = x % 100;
        nr = x / 100;
        int cif = cifControl(nr);

        if(prim(nr))
        {
            seria1[cif].punctaj += punctaj;
            seria1[cif].nrElevi++;
        }
        else
        {
            seria2[cif].punctaj += punctaj;
            seria2[cif].nrElevi++;
        }

    }

    if(cerinta == 1)sol1();
    else sol2();
}


void sol1()
{
    int mx1 = seria1[1].punctaj, mx2 = seria2[1].punctaj;
    for(int i=2;i<=9;++i)
    {
        if(mx1 < seria1[i].punctaj)mx1 = seria1[i].punctaj;
        if(mx2 < seria2[i].punctaj)mx2 = seria2[i].punctaj;
    }
    g << mx1 << ' ' << mx2;
}

void sol2()
{
    vector<Ipair>totalElevi;
    for(int i=1;i<=9;++i)
    {
        int elevi = seria1[i].nrElevi + seria2[i].nrElevi;
        if(elevi > 0)
            totalElevi.push_back( {i,elevi} );
    }
    sort(totalElevi.begin(), totalElevi.end(), [](const Ipair &a,const Ipair &b){return a.second > b.second;});

    for(Ipair &i : totalElevi)g << i.first << ' ';
}