/*
 *	Industrious Box Packer
 *
 *	g++ -O2 -o ibp ibp.cc -lpthread -lm
 *
 *      David Skinner   July 2003 (dskinner@nersc.gov)
 */


using namespace std;
#include <iostream>
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>


int collidex(int i, int j);
int collidey(int i, int j);
int collide(int i, int j);

#define CARGOSIZE 31

/*
#define VERBOSE  
*/

#define BUMPRANGE 2000

typedef struct Box {
 int xl, xh, yl, yh, yw;
 char data[CARGOSIZE];
} Box;

Box *box,*bbox;

int xcmp(const void *a, const void *b) {
 if(box[*(int *)a].xl > box[*(int *)b].xl) {
// printf(" 1 %d %d - %d %d = %d\n", *(int *)a, box[*(int *)a].xl, *(int *)b, box[*(int *)b].xl,box[*(int *)a].xl-box[*(int *)b].xl);
  return 1;
 }
 if(box[*(int *)a].xl == box[*(int *)b].xl) {
// printf(" 0 %d %d - %d %d = %d\n", *(int *)a, box[*(int *)a].xl, *(int *)b, box[*(int *)b].xl,box[*(int *)a].xl-box[*(int *)b].xl);
  return 0;
 }
// printf("-1 %d %d - %d %d = %d\n", *(int *)a, box[*(int *)a].xl, *(int *)b, box[*(int *)b].xl,box[*(int *)a].xl-box[*(int *)b].xl);
 return -1;
}

int cmp_xl(void *a, void *b) {
}


int collidex(int i, int j) {
 if(box[i].xl <= box[j].xh && box[i].xh <= box[j].xl) return 0;
 if(box[j].xl <= box[i].xh && box[j].xh <= box[i].xl) return 0;
 return 1;
}

int collidey(int i, int j) {
 if(box[i].yl <= box[j].yh && box[i].yh <= box[j].yl) return 0;
 if(box[j].yl <= box[i].yh && box[j].yh <= box[i].yl) return 0;
 return 1;
}

int collide(int i, int j) {
 if(box[i].xl <= box[j].xh && box[i].xh <= box[j].xl) return 0;
 if(box[j].xl <= box[i].xh && box[j].xh <= box[i].xl) return 0;
 if(box[i].yl <= box[j].yh && box[i].yh <= box[j].yl) return 0;
 if(box[j].yl <= box[i].yh && box[j].yh <= box[i].yl) return 0;
 return 1;
}

int main(int argc, char *argv[]) {

  int nbox=0,i,j,nbump,bump[4096];
  int xl,xh,yl,yw,yh,done;
  int xmin=9999999999,xmax=-1,ymin=9999999999,ywmax=-1,ymax=-1;
  int *xindex, *xrank,xblb,xbub,xi;
  char line[1024], dbuf[CARGOSIZE];
  FILE *in;

  if(argc == 2) {
   in = fopen(argv[1],"r");
  }

  if(!in) {printf("ERROR: can't open file '%s'\n",argv[1]); exit(1);}

  while(EOF != fscanf(in,"%d %d %d %s\n", &xl,&xh,&yw,dbuf)) {
   if(xl < xmin) xmin=xl;
   if(xh > xmax) xmax=xh;
   if(yw > ywmax) ywmax=yw;
   nbox++;
  }
  fseek(in,0L,SEEK_SET);

#ifdef VERBOSE
   printf("#BOXES %d  ( %d %d ) ( %d %d )\n", nbox, xmin, xmax,0,ywmax);
#endif

  box = new Box[nbox];
  xindex = new int[nbox];
  xrank = new int[nbox];


  for(i=0;i<nbox;i++) {

   fscanf(in,"%d %d %d %s\n", &box[i].xl, &box[i].xh, &box[i].yw, box[i].data);
   box[i].yl = 0;
   box[i].yh = box[i].yl+box[i].yw;
  }

  for(i=0;i<nbox;i++) xrank[i] = i;
  qsort(xrank,nbox,sizeof(int),&xcmp);
  for(i=0;i<nbox;i++) xindex[xrank[i]] = i;

/*
  for(i=0;i<nbox;i++)  {
   printf("#QSORT %d %d %d %d\n", i, xrank[i], xindex[i], box[xrank[i]].xl);
  }
*/

  for(i=0;i<nbox;i++) {
   nbump = 0;


/* Full N*N *********************************************************/
/*
   for(j=0; j<i; j++) {
    if(collidex(i,j)) bump[nbump++] = j;
   }
*/

/* Bump List (sub N*N) **********************************************/
/* xrank[i]  tell me the index of the ith largest element of x      */
/* xindex[i] tell me the index of the ith element of x in  sorted x */
/********************************************************************/

   xi = xindex[i];
   xblb = ((xi>BUMPRANGE)?(xi-BUMPRANGE):(0));
   xbub = ((nbox-xi>BUMPRANGE)?(xi+BUMPRANGE):(nbox));
#ifdef VERBOSE
   printf("#HIST %d  %d : ", xblb, xbub);
#endif
   for(j=xblb; j<xbub; j++) {
    if(xrank[j] < i && collidex(i,xrank[j])) bump[nbump++] = xrank[j];
   }



/* bsearch NlogN  ***************************************************/
/********************************************************************/
/* ? */

/* Common  **********************************************************/
#ifdef VERBOSE
   printf("#BUMP %d  %d : ", i, nbump);
   for(j=0; j<nbump; j++) {
    printf("%d ",bump[j]);
   }
   printf("\n");
/*
   for(j=0; j<nbump; j++) {
    printf("#BUMP %d %d \n",i, bump[j]);
   }
*/
#endif

   done = 0;
   box[i].yl = 0;
   while(!done) {
    done = 1;
    for(j=0; j<nbump; j++) {
     if(collidey(i,bump[j])) {
      box[i].yl = box[bump[j]].yh+1;
      box[i].yh = box[i].yl+box[i].yw;
      done = 0;
     }
    }
   }

   printf("%d %d %d %d %s\n",
    box[i].xl, box[i].xh, box[i].yl, box[i].yh, box[i].data);
  }
  return 0;
}