#include <stdio.h>
#include <math.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/times.h>
#include <time.h>
#include <limits.h>

#define DEBUG 0

#define MAXPICTURES	26

struct Picture {
	int w0;
	int h0;
	int x;
	int y;
	int w;
	int h;
	int bestX;
	int bestY;
	int bestW;
	int bestH;
	float ratio;
};

int pageW;
int pageH;
int minArea;
Picture pictures[MAXPICTURES];
int nPictures;

int bestScore;
int bestTieBreak;
int timeLimit= 58;

int timeExceeded()
{
	static int calls= 0;
	struct tms t;
	times(&t);
	calls++;
	return (calls+1)*(t.tms_utime+t.tms_stime) > calls*timeLimit*CLK_TCK;
}

void readFile(const char* name)
{
	FILE* in= fopen(name,"r");
	if (in == NULL) {
		fprintf(stderr,"cant read %s\n",name);
		exit(0);
	}
	char buf[100];
	fgets(buf,100,in);
	sscanf(buf,"PAGE %d %d",&pageW,&pageH);
	minArea= pageW*pageH/100;
	nPictures= 0;
	while (fgets(buf,100,in) != NULL) {
		int x,y;
		sscanf(buf,"%*c %d %d",&x,&y);
		Picture* p= &pictures[nPictures++];
		memset(p,0,sizeof(Picture));
		if (y < x) {
			p->w0= y;
			p->h0= x;
		} else {
			p->w0= x;
			p->h0= y;
		}
		p->ratio= p->h0 / (double)p->w0;
	}
	fclose(in);
}

void printPics(const char* lbl, int pw, int ph, Picture** pics, int n)
{
	fprintf(stderr,"%s %d %d\n",lbl,pw,ph);
	for (int i=0; i<n; i++) {
		Picture* p= pics[i];
		fprintf(stderr,"%c %5d %5d %5d %5d %f %f\n",p-pictures+'A',
		  p->w,p->h,p->x,p->y,
		  p->ratio,p->h>p->w?p->h/(float)p->w:p->w/(float)p->h);
	}
}

void saveBest(int score)
{
#if DEBUG
	fprintf(stderr,"%d\n",score);
#endif
	if (score > bestScore)
		return;
	int minA= 0x7fffffff;
	int maxA= 0;
	for (int i=0; i<nPictures; i++) {
		Picture* p= &pictures[i];
		int a= p->w*p->h;
		if (minA > a)
			minA= a;
		if (maxA < a)
			maxA= a;
		if (a < minArea) {
#if DEBUG
			fprintf(stderr," area problem %c %d %d\n",
			  i+'A',a,minArea);
#endif
			return;
		}
		float r= p->h>p->w ? p->h/(float)p->w : p->w/(float)p->h;
		if (r-p->ratio<-.02 || r-p->ratio>.02) {
#if DEBUG
			fprintf(stderr," ratio problem %c %lf %lf\n",
			  i+'A',r,p->ratio);
#endif
			return;
		}
	}
	if (score==bestScore && maxA-minA>=bestTieBreak)
		return;
	bestScore= score;
	bestTieBreak= maxA-minA;
#if DEBUG
	fprintf(stderr,"new best %d %d\n",bestScore,bestTieBreak);
#endif
	for (int i=0; i<nPictures; i++) {
		Picture* p= &pictures[i];
		p->bestX= p->x;
		p->bestY= p->y;
		p->bestW= p->w;
		p->bestH= p->h;
#if DEBUG
		fprintf(stderr,"%c %5d %5d %5d %5d %f %f\n",i+'A',
		  p->bestW,p->bestH,p->bestX,p->bestY,
		  p->ratio,p->h>p->w?p->h/(float)p->w:p->w/(float)p->h);
#endif
	}
}

#define CUTOFF 26

//	recursive picture packing heuristic
//	pics is a list of pictures that remain to be placed
//	n is the number of pictures that remain
//	pw is the remaining page width
//	ph is the remaining page height
//	waste is the number of pixels wasted so far (always zero currently)
//
//	Selects a slice of the remaining page and packs some pictures in it,
//	then recursively packs the remaining pictures in the remaining
//	part of the page.
//	The recursion is stopped as soon as a feasible solution is found
//	if n>CUTOFF (this feature is disabled)
//
int dcfit1(Picture** pics, int n, int pw, int ph, int waste)
{
#if DEBUG
	fprintf(stderr,"dcfit1(%d,%d,%d,%d)\n",n,pw,ph,waste);
#endif
	if (n <= 0) {
		waste+= pw*ph;
		saveBest(waste);
		return waste;
	}
	if (pw*ph < n*minArea)
		return 999999999;
	if (timeExceeded())
		return 999999999;
	int bestS= 999999999;
	for (int i=0; i<n; i++) {
		float r= 0;
		for (int j=0; j<=i; j++)
			r+= pics[j]->ratio;
		if (ph/r <= pw) {
			// pack pictures 0 through i vertically in a
			// vertical slice of the page
			float w= ph/r;
			float s= 0;
			int h= 0;
			for (int j=0; j<=i; j++) {
				Picture* p= pics[j];
				s+= p->ratio*w;
				p->h= (int)(s+.5) - h;
				h+= p->h;
				p->y= ph-h;
			}
			if (h != ph) {
				pics[i]->h+= ph-h;
				pics[i]->y= 0;
			}
			// try width based on max. aspect ratio
			int maxW= 0;
			for (int j=0; j<=i; j++) {
				Picture* p= pics[j];
				p->w= (int)ceil(p->h/(p->ratio+.02));
				if (maxW < p->w)
					maxW= p->w;
			}
			for (int j=0; j<=i; j++) {
				Picture* p= pics[j];
				p->w= maxW;
				p->x= pw-maxW;
				float r= p->w<p->h ? p->h/(float)p->w :
				  p->w/(float)p->h;
				if (-.02>=r-p->ratio || r-p->ratio>=.02 ||
				  p->w*p->h<minArea)
					maxW= 0;
			}
			if (maxW > 0) {
#if DEBUG
				printPics("1",pw,ph,pics,i+1);
#endif
				int s= dcfit1(pics+i+1,n-i-1,pw-maxW,ph,waste);
				if (bestS > s) {
					bestS= s;
					if (n>CUTOFF)
						return s;
				}
			}
			// try width based on min. aspect ratio
			maxW= 0;
			for (int j=0; j<=i; j++) {
				Picture* p= pics[j];
				p->w= (int)floor(p->h/(p->ratio-.02));
				if (maxW < p->w)
					maxW= p->w;
			}
			if (maxW > pw)
				maxW= pw;
			for (int j=0; j<=i; j++) {
				Picture* p= pics[j];
				p->w= maxW;
				p->x= pw-maxW;
				float r= p->w<p->h ? p->h/(float)p->w :
				  p->w/(float)p->h;
				if (-.02>=r-p->ratio || r-p->ratio>=.02 ||
				  p->w*p->h<minArea)
					maxW= 0;
			}
			if (maxW > 0) {
#if DEBUG
				printPics("1c",pw,ph,pics,i+1);
#endif
				int s= dcfit1(pics+i+1,n-i-1,pw-maxW,ph,waste);
				if (bestS > s) {
					bestS= s;
					if (n>CUTOFF)
						return s;
				}
			}
		} else if (i == 0) {
			// if picture 0 won't fit vertically by itself
			// in a vertical slice try a horizontal slice
			Picture* p= pics[i];
			p->w= pw;
			p->h= (int)floor((p->ratio+.02)*pw);
			if (p->h > ph)
				p->h= ph;
			p->x= 0;
			p->y= ph-p->h;
			float r= p->w<p->h ? p->h/(float)p->w :
			  p->w/(float)p->h;
			if (-.02<r-p->ratio && r-p->ratio<.02 &&
			  p->w*p->h>=minArea) {
#if DEBUG
				printPics("1a",pw,ph,pics,i+1);
#endif
				int s= dcfit1(pics+1,n-1,pw,p->y,waste);
				if (bestS > s) {
					bestS= s;
					if (n>CUTOFF)
						return s;
				}
			}
			p->h= (int)ceil((p->ratio-.02)*pw);
			if (p->h<p->w && p->w/(float)p->h-p->ratio>.02)
				p->h++;
			if (p->h > ph)
				p->h= ph;
			p->y= ph-p->h;
			r= p->w<p->h ? p->h/(float)p->w :
			  p->w/(float)p->h;
			if (-.02<r-p->ratio && r-p->ratio<.02 &&
			  p->w*p->h>=minArea) {
#if DEBUG
				printPics("1b",pw,ph,pics,i+1);
#endif
				int s= dcfit1(pics+1,n-1,pw,p->y,waste);
				if (bestS > s) {
					bestS= s;
					if (n>CUTOFF)
						return s;
				}
			}
		}
		if (pw/r <= ph) {
			// pack pictures 0 through i horizontally in a
			// horizontal slice of the page
			float h= pw/r;
			float s= 0;
			int w= 0;
			for (int j=0; j<=i; j++) {
				Picture* p= pics[j];
				s+= p->ratio*h;
				p->w= (int)(s+.5)-w;
				w+= p->w;
				p->x= pw-w;
			}
			if (w != pw) {
				pics[i]->w+= pw-w;
				pics[i]->x= 0;
			}
			int maxH= 0;
			for (int j=0; j<=i; j++) {
				Picture* p= pics[j];
				p->h= (int)ceil(p->w/(p->ratio+.02));
				if (maxH < p->h)
					maxH= p->h;
			}
			for (int j=0; j<=i; j++) {
				Picture* p= pics[j];
				p->h= maxH;
				p->y= ph-maxH;
				float r= p->w<p->h ? p->h/(float)p->w :
				  p->w/(float)p->h;
				if (-.02>=r-p->ratio || r-p->ratio>=.02 ||
				  p->w*p->h<minArea)
					maxH= 0;
			}
			if (maxH > 0) {
#if DEBUG
				printPics("2",pw,ph,pics,i+1);
#endif
				int s= dcfit1(pics+i+1,n-i-1,pw,ph-maxH,waste);
				if (bestS > s) {
					bestS= s;
					if (n>CUTOFF)
						return s;
				}
			}
			maxH= 0;
			for (int j=0; j<=i; j++) {
				Picture* p= pics[j];
				p->h= (int)floor(p->w/(p->ratio-.02));
				if (maxH < p->h)
					maxH= p->h;
			}
			if (maxH > ph)
				maxH= ph;
			for (int j=0; j<=i; j++) {
				Picture* p= pics[j];
				p->h= maxH;
				p->y= ph-maxH;
				float r= p->w<p->h ? p->h/(float)p->w :
				  p->w/(float)p->h;
				if (-.02>=r-p->ratio || r-p->ratio>=.02 ||
				  p->w*p->h<minArea)
					maxH= 0;
			}
			if (maxH > 0) {
#if DEBUG
				printPics("2c",pw,ph,pics,i+1);
#endif
				int s= dcfit1(pics+i+1,n-i-1,pw,ph-maxH,waste);
				if (bestS > s) {
					bestS= s;
					if (n>CUTOFF)
						return s;
				}
			}
		} else if (i == 0) {
			// if picture 0 won't fit horizontally by itself
			// in a horizontal slice try a vertical slice
			Picture* p= pics[i];
			p->h= ph;
			p->w= (int)floor((p->ratio+.02)*ph);
			if (p->w > pw)
				p->w= pw;
			p->x= pw-p->w;
			p->y= 0;
			float r= p->w<p->h ? p->h/(float)p->w :
			  p->w/(float)p->h;
			if (-.02<r-p->ratio && r-p->ratio<.02 &&
			  p->w*p->h>=minArea) {
#if DEBUG
				printPics("2a",pw,ph,pics,i+1);
#endif
				int s= dcfit1(pics+1,n-1,p->x,ph,waste);
				if (bestS > s) {
					bestS= s;
					if (n>CUTOFF)
						return s;
				}
			}
			p->w= (int)ceil((p->ratio-.02)*ph);
			if (p->w<p->h && p->h/(float)p->w-p->ratio>.02)
				p->w++;
			if (p->w > pw)
				p->w= pw;
			p->x= pw-p->w;
			r= p->w<p->h ? p->h/(float)p->w :
			  p->w/(float)p->h;
			if (-.02<r-p->ratio && r-p->ratio<.02 &&
			  p->w*p->h>=minArea) {
#if DEBUG
				printPics("2b",pw,ph,pics,i+1);
#endif
				int s= dcfit1(pics+1,n-1,p->x,ph,waste);
				if (bestS > s) {
					bestS= s;
					if (n>CUTOFF)
						return s;
				}
			}
		}
	}
#if DEBUG
	fprintf(stderr,"%d\n",bestS);
#endif
	return bestS;
}

//	Makes a randomized list of pictures and then applies the packing
//	heuristic.
//
void randFit()
{
	Picture* pics[MAXPICTURES];
	for (int i=0; i<nPictures; i++)
		pics[i]= &pictures[i];
	for (int i=0; i<nPictures; i++) {
		int j= (int)(drand48()*nPictures);
		Picture* t= pics[i];
		pics[i]= pics[j];
		pics[j]= t;
	}
	dcfit1(pics,nPictures,pageW,pageH,0);
}

int ratioComp(const void*v1, const void*v2)
{
	Picture* p1= *(Picture**)v1;
	Picture* p2= *(Picture**)v2;
	if (p1->ratio < p2->ratio)
		return 1;
	if (p1->ratio > p2->ratio)
		return -1;
	return 0;
}

//	Sorts the pictures in decreasing aspect ratio order and
//	then applies the packing heuristic.
//
void dratiofit()
{
	Picture* pics[MAXPICTURES];
	for (int i=0; i<nPictures; i++)
		pics[i]= &pictures[i];
	qsort(pics,nPictures,sizeof(Picture*),ratioComp);
	dcfit1(pics,nPictures,pageW,pageH,0);
}

int main(int argc, char** argv)
{
	while (argc>2 && argv[1][0]=='-') {
		switch (argv[1][1]) {
		 case 't':
			timeLimit= atoi(argv[1]+2);
			break;
		}
		argc--;
		argv++;
	}
	readFile(argv[1]);
	bestScore= 0x7fffffff;
	bestTieBreak= 0x7fffffff;
	dratiofit();
	for (int i=0; bestScore>0 && i<nPictures*nPictures &&
	  !timeExceeded(); i++)
		randFit();
	for (int i=0; i<nPictures; i++) {
		Picture* p= &pictures[i];
		printf("%c %5d %5d %5d %5d\n",i+'A',
		  p->bestW,p->bestH,p->bestX,p->bestY);
	}
	exit(0);
}