/* 
 * Problema 18 (variante).  Ordenação por colunas.  Versão de ordenação
 * indireta.  Queremos aqui ordenar datas (como no Problema 18 original). 
 * 
 * Queremos v tal que as datas em A são, em ordem, 
 * 
 * A[v[0]], A[v[1]], ..., A[v[M - 1]]
 * 
 * Isso evita movimentação de dados no processo de ordenação (que é
 * algo relevante quando ordenamos objetos "grandes").
 */

#include <stdio.h>

#define MMAX 100
#define NMAX 100

void ordene_por_col(int v[], int A[][NMAX], int M, int c);
void exch(int v[], int i, int j);
void ordene_datas_ind(int v[], int D[][3], int M);
int leia_datas(int D[][3]);
void imprima_datas_ind(int v[], int D[][3], int M);
  
int main()
{
  int D[MMAX][3];
  int M = leia_datas(D);
  int v[MMAX], i;

  for (i = 0; i < M; i++) 
    v[i] = i;
  printf("Ordem original:\n");
  imprima_datas_ind(v, D, M);

  ordene_datas_ind(v, D, M);

  printf("\nDatas ordenadas:\n");
  imprima_datas_ind(v, D, M);
  
  return 0;
}

void ordene_por_col_ind(int v[], int A[][NMAX], int M, int c)
{
  int i, j;
  for (i = 1; i < M; i++)
    for (j = i; j > 0 && A[v[j]][c] < A[v[j - 1]][c]; j--) 
      exch(v, j - 1, j);
}

void exch(int v[], int i, int j) 
{
  int t = v[i];
  v[i] = v[j];
  v[j] = t;
}

void ordene_datas_ind(int v[], int D[][3], int M)
{
  int i, j;
  int A[MMAX][NMAX];

  for (i = 0; i < M; i++) 
    for (j = 0; j < 3; j++) 
      A[i][j] = D[i][j];
  
  ordene_por_col_ind(v, A, M, 0);
  ordene_por_col_ind(v, A, M, 1);
  ordene_por_col_ind(v, A, M, 2);

  for (i = 0; i < M; i++) 
    for (j = 0; j < 3; j++) 
      D[i][j] = A[i][j];
}

void imprima_datas_ind(int v[], int D[][3], int M)
{
  int i;

  for (i = 0; i < M; i++) 
    printf("%2d %2d %4d\n", D[v[i]][0], D[v[i]][1], D[v[i]][2]);
}

int leia_datas(int D[][3])
{
  int i = 0;

  while (i < MMAX && scanf("%d %d %d", &D[i][0], &D[i][1], &D[i][2]) == 3) 
    i++;

  return i;
}