#include <iostream>
#include <map>
#include <vector>
#include <set>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;

int main() {
    int n, b;
    while (cin >> n >> b, n || b) {
        cin.ignore();
        vector<vector<string> > ballots(b);
        set<string> all_candidates;

        for (int i = 0; i < b; ++i) {
            string line;
            getline(cin, line);
            stringstream ss(line);
            string name;
            while (ss >> name) {
                ballots[i].push_back(name);
                all_candidates.insert(name);
            }
        }

        set<string> eliminated;
        while (true) {
            map<string, int> count;
            int viable = 0;
            for (int i = 0; i < b; ++i) {
                for (int j = 0; j < ballots[i].size(); ++j) {
                    if (eliminated.count(ballots[i][j]) == 0) {
                        count[ballots[i][j]]++;
                        ++viable;
                        break;
                    }
                }
            }

            string winner = "";
            for (map<string, int>::iterator it = count.begin(); it != count.end(); ++it) {
                if (it->second > viable / 2) {
                    winner = it->first;
                    break;
                }
            }
            if (!winner.empty()) {
                cout << winner << " won" << endl;
                break;
            }

            if (count.empty()) break;

            int min_votes = b + 1;
            for (map<string, int>::iterator it = count.begin(); it != count.end(); ++it) {
                if (it->second < min_votes)
                    min_votes = it->second;
            }

            vector<string> to_eliminate;
            for (map<string, int>::iterator it = count.begin(); it != count.end(); ++it) {
                if (it->second == min_votes)
                    to_eliminate.push_back(it->first);
            }

            if (to_eliminate.size() == count.size()) {
                sort(to_eliminate.begin(), to_eliminate.end());
                cout << "it is a tie between " << to_eliminate[0];
                for (size_t i = 1; i < to_eliminate.size(); ++i)
                    cout << " and " << to_eliminate[i];
                cout << endl;
                break;
            }

            for (size_t i = 0; i < to_eliminate.size(); ++i)
                eliminated.insert(to_eliminate[i]);
        }
    }
    return 0;
}