#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int ncandidates;
char **candidates;
int  *tally;
int nvotes;
char **votes;

int compare (const void * a, const void * b)
{
    char *s1 = (char *) (*(char **)a);
    char *s2 = (char *) (*(char **)b);

    return strcmp(s1,s2);
}

int FindCandidate(char *s)
{
    int low=0,high=ncandidates-1;
    int try;

    while (low != high) {
        try = (low + high)/2;
        if (strcmp(s,candidates[try]) < 0) {
            high = try-1;
        }
        if (strcmp(s,candidates[try]) > 0) {
            low = try+1;
        }
        if (strcmp(s,candidates[try]) == 0) {
            return try;
        }
    }

    return (low);
}

main()
{
    int i,j;
    char line[1024];

    while(1){
      int done=0;
      fscanf(stdin,"%d %d\n",&ncandidates,&nvotes);
      if(ncandidates == 0)
	exit(0);
      
      
      candidates = (char **) malloc(ncandidates * sizeof(char*));
      tally = (int *) malloc(ncandidates * sizeof(int));
      votes = (char **) malloc(nvotes * sizeof(char*));
      
      i=j=0;
      while (i<nvotes && fgets(line,sizeof(line),stdin)) {
	if (line[strlen(line)-1] == '\n')
	  line[strlen(line)-1] = '\0';
	
	votes[i++] = strdup(line);
	
        // scan the line looking for any new candidates to include
        if (j<ncandidates) {
	  int k;
	  char *s = strtok(line," \t");
	  while (j<ncandidates && s) {
	    for (k=0 ; k<j && strcmp(candidates[k],s) ; k++)
	      ;
	    if (k==j) {
	      candidates[j++] = strdup(s);
	    }
	    s = strtok(NULL," \t");
	  }
        }
      }
      
      // just in case the file was "short"
      nvotes = i;
      ncandidates = j;
      
      qsort(candidates,ncandidates,sizeof(char*),compare);
      
      for (j=0 ; j<ncandidates ; j++) {
        tally[j] = 0;
      }
      
      while (!done) {
        int counted=0;
        int maxvotes,minvotes;
        int cleft=0;
	
        for (i=0 ; i<nvotes ; i++) {
	  char *s;
	  strcpy(line,votes[i]);
	  s = strtok(line," \t");
	  while (s) {
	    j=FindCandidate(s);
	    if (tally[j] != -1) {
	      tally[j]++;
	      counted++;
	      break;
	    }
	    else 
	      s = strtok(NULL," \t");
	  }
        }
	
        maxvotes=-1;
        minvotes=counted+1;
        // find candidate with most/least votes... 
        cleft=0;
        for (j=0 ; j<ncandidates ; j++) {
	  if (tally[j] != -1) {
	    cleft++;
	    //printf("%s got %d votes\n",candidates[j],tally[j]);
	    if (tally[j] > maxvotes)    maxvotes = tally[j];
	    if (tally[j] < minvotes)    minvotes = tally[j];
	  }
        }

        // did someone get greater than 50% of the vote?
        if (maxvotes > counted/2) {
	  for (j=0 ; j<ncandidates ; j++) {
	    if (tally[j] == maxvotes)
	      printf("%s won\n",candidates[j]);
	  }
	  done=1;
        }

        // are we down to 2 candidates with exactly the same number of votes?
        if (cleft*maxvotes == counted) {
	  printf("it is a tie between ");
	  for (j=0 ; j<ncandidates ; j++) {
	    if (tally[j] == maxvotes) {
	      printf("%s",candidates[j]);
	      if (cleft-- > 1)
		printf(" and ");
	      else
		printf("\n");
	    }
	  }
	  done=1;
        }

        // if not... find candidate(s) with fewest votes and eliminate him(them)
        for (j=0 ; !done && j<ncandidates ; j++) {
	  if (tally[j] <= minvotes) {
	    //if (tally[j] > -1) printf ("eliminating %s\n",candidates[j]);
	    tally[j] = -1;
	  }
	  else
	    tally[j] = 0;
        }
      }
    }
}