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

// prototype
void pp(char *, int , int );
int searchMajority();
void votesExchange( int );

char *matrix;
int votes,
    candidates,
    *sum;

void pp(char *a, int x, int y)
{
  int i,
      j;

  for ( i = 1; i <= x; ++i) {
    for ( j = 1; j <= y; ++j) {
      putchar(*a++);
    }
    puts("");
  }
}

int searchMajority()
{
  int i;
  char *p = matrix;

  // 機能１：
  // sumに集計結果をセットする 。
  for ( i = 0; i < candidates; ++i) {
    sum[i] = 0;
  }
  for ( i = 0; i < votes; ++i) {
    // printf("matrix %c\n", *p);
    sum[*p - '1']++;
    p += candidates;
  }

  // for ( i = 0; i < candidates; ++i) {
  //   printf("sum[%d] = %d\n", i, sum[i]);
  // }

  // 機能２：
  // 過半数獲得候補者が有れば、候補者番号(1~candidates)を返す。
  // 過半数候補者が無ければ、0を返す。
  for (i = 0; i < candidates; ++i) {
    if (sum[i] > votes / 2) {
      return i;
    }
  }
  return 0;
}

void votesExchange(int n)
{
  char t,
       *p = matrix;
  int i,
      min = votes;

  printf("%3d 回目の入替 -> ", n);
  for ( i = 1; i < candidates; ++i) {
    if ((min > sum[i]) && (sum[i])) {
      min = sum[i];
    }
  }
  printf("最小得票数 = %6d\n", min);
  for ( i = 0; i < votes; ++i) {
    if (sum[*p - '1'] == min) {
      // swap
      t = *p;
      *p = *(p + n);
      *(p + n) = t;
    }
    p += candidates;
  }
}


int main()
{
  FILE *fp;
  char c,
       *p,
       buf[100],
       // s[100],
       fname[] = "c672-3.c.in";
  int i,
      n,/* 入替対象列 */
      max,/* 最大得票数 */
      majority = 0;/* 過半数を獲得した候補者番号 */

  // 入力ファイルopen
  fp     = fopen(fname, "r");
  if ( fp == NULL ) {
    printf( "%sファイルが開けません\n", fname );
    return -1;
  }

  // 候補者数をファイルから読み込む
  fgets(buf, 100, fp);
  p = strchr(buf, '=');
  if (p == NULL) {
    printf("候補者数を読み込めません\n" );
    return -1;
  }
  candidates = atoi(p + 1);

  // 投票者数をファイルから読み込む
  fgets(buf, 100, fp);
  p = strchr(buf, '=');
  if (p == NULL) {
    printf("投票者数を読み込めません\n" );
    return -1;
  }
  votes = atoi(p + 1);

  // 集計エリア確保
  matrix = (char *)malloc(sizeof(char) * candidates * votes);
  sum = (int *)malloc(sizeof(int) * candidates);

  // ファイルからデータ読込
  p = matrix;
  i = votes * candidates;
  while ((c = fgetc(fp)) != EOF) {
    if (c != '\n') {
      *p++ = c;
      if (--i == 0) {
        break;
      }
    }
  }

  n = 1;
  majority = searchMajority();
  while (!majority && (n < candidates)) {
    votesExchange(n);
    majority = searchMajority();
    ++n;
  }

  if (majority) { /* 入替による過半数が有った場合 */
    printf("majority = %d\n", majority);
  } else { /* 入替による過半数が無かった場合、最大得票数の候補を探す（複数の可能性あり） */
    max = sum[0];/* 最大得票数を探す */
    for (i = 0; i < candidates; ++i) {
      if (max < sum[i]) {
        max = sum[i];
      }
    }
    for (i = 0; i < candidates; ++i) { /* 最大得票数に一致する候補者番号を出力する */
      if (sum[i] == max) {
        printf("majority = %d\n", i);
      }
    }
  }

  return 0;
}