#include <fstream>
using namespace std;

ifstream fin("aeriana.in");
ofstream fout("aeriana.out");

int prim(int n){
    int ok=1;
    for(int i=2;i*i<n && ok==1;i++){
        if(n%i==0) ok=0;
        int k=n/i;
        if(n%k==0) ok=0;
    }
    return ok;
}

int sumcif(int n){
    int s=0;
    while(n>0){
        s+=n%10;
        n=n/10;
    }
    return s;
}

int main(){
    int c,n;
    fin>>c>>n;
    if(c==1){
    int a1,a2,h1,m1,h2,m2;
    int mmax=0;
      for(int i=1;i<=n;i++)
      {
        fin>>a1>>a2>>h1>>m1>>h2>>m2;
        int total1=0,total2=0;
        total1=h1*60+m1;
        total2=h2*60+m2;
        if(h2<h1) total2+=24*60;
        if(total2-total1>mmax){
            mmax=total2-total1;
        }
      }
      fout<<mmax/60<<" "<<mmax%60;
    }
    else{
    int a1,a2,h1,m1,h2,m2;
    int mmax=0;
      for(int i=1;i<=n;i++)
      {
        fin>>a1>>a2>>h1>>m1>>h2>>m2;
        if(prim(a1)==1){
            int v=sumcif(a1);
            if(v!=0){
            if((a2%v)==0){
                int aux1,aux2;
                aux1=h1;
                aux2=m1;
                h1=h2;
                m1=m2;
                h2=aux1;
                m2=aux2;
            }}
            else{
                int aux1,aux2;
                aux1=h1;
                aux2=m1;
                h1=h2;
                m1=m2;
                h2=aux1;
                m2=aux2;
            }
        }
        int total1=0,total2=0;
        total1=h1*60+m1;
        total2=h2*60+m2;
        if(h2<h1) total2+=24*60;
        if(total2-total1>mmax){
            mmax=total2-total1;
        }
      }
      fout<<mmax/60<<" "<<mmax%60;
    }
}