#!/usr/bin/python
# Written by "Kuno" for the GLOSSY POTM
import time
import sys
import string
import math
from random import choice

MAXTIME = 60.0 # secs

if sys.version < '2.3': # fred's server has really old software
    from operator import add
    def sum(a):
        return reduce (add, a)
    def enumerate(a):
        return zip(range(len(a)), a)

class Rect:
    """Rectangle - name, size, position"""
    def __init__(self, a, min_area):
        self.label = a[0]
        self.w, self.h = int(a[1]), int(a[2])
        if (min_area > 0) and (self.w < self.h): # rotate the pics to wide format (but not the PAGE)
            self.w, self.h = self.h, self.w
        self.a = float(self.w)/self.h            # aspect ratio
        self.i_a = 1.0/self.a                    # rotated aspect ratio
        self.min_size = math.sqrt(min_area/self.a) # min_size = minimal height
        self.i_min_size = math.sqrt(min_area/self.i_a)
        self.max_a = self.a + 0.02
        self.min_a = self.a - 0.02
        if self.w*100 <= self.h*102: # a < 1.02: both orientations can be combined
            self.min_a = 1.0/self.max_a
        self.i_min_a = 1.0/self.max_a
        self.i_max_a = 1.0/self.min_a
        self.min_size_h = int(math.sqrt(min_area/self.max_a)+0.99999)
        self.i_min_size_h = int(math.sqrt(min_area/self.i_max_a)+0.99999)
        self.x, self.y = -1, -1

    def rotate(self):
        self.w, self.h = self.h, self.w
        self.a, self.i_a = self.i_a, self.a
        self.min_size, self.i_min_size = self.i_min_size, self.min_size
        self.min_a, self.i_min_a = self.i_min_a, self.min_a
        self.max_a, self.i_max_a = self.i_max_a, self.max_a
        self.min_size_h, self.i_min_size_h = self.i_min_size_h, self.min_size_h

    def unrotate(self):
        if self.w < self.h:
            self.rotate()

    def get_solution(self, rotated): # rotated means "the page is rotated", not "this rect is rotated inside the page"
        if not rotated:
            return "%s %5d %5d %5d %5d" % (self.label, self.w, self.h, self.x, self.y)
        else:
            return "%s %5d %5d %5d %5d" % (self.label, self.h, self.w, self.y, self.x)


class Group:
    """Group of Rectangles that will be arranged in a line"""
    def __init__(self):
        self.rects=[]
        self.a = 0.0
        self.i_a = 0.0
        self.min_size = 0.0  # height
        self.min_size2 = 0.0 # width (= self.min_size*self.a)
        self.min_size_h = 0

    def append(self, r):
        self.rects.append(r)
        self.a += r.a
        self.i_a = 1.0/self.a
        self.min_size = max(self.min_size, r.min_size)
        self.min_size2 = self.min_size*self.a
        self.min_size_h = max(self.min_size_h, r.min_size_h)

    def pop_random(self):
        r = self.rects.pop(0) # it's faster not to use random here (r = self.rects.pop(random.randrange(len(self.rects))))
        self.a -= r.a
        self.i_a = 1.0/self.a
        #if r.min_size == self.min_size:          # I like "dangerous" float comparisons
        #if r.min_size >= self.min_size - 0.0001: # didn't work though
        if r.min_size == self.min_size:           # turns out it DOES work, after all
            self.min_size = max([s.min_size for s in self.rects])
        self.min_size2 = self.min_size*self.a
        if r.min_size_h == self.min_size_h:
            self.min_size_h = max([s.min_size_h for s in self.rects])
        return r

    def min_a(self):
        return sum([r.min_a for r in self.rects])

    def place_stretch(self, y, w0, h, max_h = 0):
        """position (0, y), maximal width, maximal height, max height for maximal width"""
        rs = self.rects
        h = min(h, int(w0/self.min_a())) # can't be higher than this
        rs.sort(lambda r, s: cmp(r.a, s.a))             # try to maximise the smallest pic
        while True: # in some cases, the height calculated above might be impossible - a smaller one will be used
            t_max_size = 0 # total maximum size
            cont = False
            for r in rs:
                r.max_size = int(h*r.max_a)
                r.min_w = int(h*r.min_a+0.99999)
                if r.max_size < r.min_w: # baaaaad, like height = 1495, r.a = 10.0
                    if h < max_h:
                        h += 1
                    else:
                        h -= 1
                        max_h = 0
                    cont = True
                    break
                r.t_max_size = t_max_size
                t_max_size += r.max_size
            if cont:
                continue
            t_min_rest = w0
            for i in range(len(rs)-1, -1, -1):
                r=rs[i]
                t_min_rest -= r.min_w
                r.t_min_rest = t_min_rest
                if r.t_min_rest < r.t_max_size: # xxx
                    r.w = r.min_w
                else:
                    n = i + 1
                    rest_w = t_min_rest + r.min_w
                    break
            else:
                h -= 1
                max_h = 0
                continue

            for i in range(n):
                r = rs[i]
                r.w = min(r.max_size, rest_w/(n-i))
                rest_w -= r.w
            if (rest_w > 0) and (max_h > h):
                h += 1
                continue

            x = 0
            for r in rs:
                r.x, r.y, r.h = x, y, h
                x += r.w
            return h

    def max_a(self):
        return sum([r.max_a for r in self.rects])

    def compute_sizes(self, w):
        s = int(w/self.max_a())
        while sum([int(s*r.max_a) for r in self.rects]) > w:
            s -= 1
        while sum([int(s*r.max_a) for r in self.rects]) < w:
            s += 1
        self.min_size_full = s
        s = int(w/self.min_a())
        while sum([int(s*r.min_a+0.99999) for r in self.rects]) < w:
            s += 1
        while sum([int(s*r.min_a+0.99999) for r in self.rects]) > w:
            s -= 1
        self.max_size_full = s

class Groups:
    """Partition pics into groups"""
    def __init__(self, num_groups, pics):
        self.groups=[Group() for i in range(num_groups)]
        for i in range(len(pics)):
            self.groups[i % num_groups].append(pics[i])

    def calculate(self, w):
        """align the groups to form a perfect rectangle"""
        self.min_size2 = max([g.min_size2 for g in self.groups])
        if self.min_size2 > w:
            self.groups.sort(lambda g, h: cmp(g.min_size2, h.min_size2))
            if self.groups[-1].min_size2 > w and self.groups[0].min_size2 < w: # and len(self.groups[-1].rects) > 1: # the ValueError should catch it
                self.groups[0].append(self.groups[-1].pop_random())
                self.calculate(w) # shudder - this could recurse indefinitely
            else:
                raise ValueError # no way to produce valid output
        else:
            self.aligned_a = 1/sum([g.i_a for g in self.groups])

    def place_stretch(self, p):
        w, h = p.w, p.h
        if self.min_size2 > w:
            return False
        self.groups.sort(lambda g, h: cmp(h.min_size_h, g.min_size_h))
        t_min_size, t_min_size_full, t_max_size_full = 0, h, h # total minimal size, total min size using full width, total max size using full width
        for g in self.groups:
            g.t_min_size = t_min_size
            t_min_size += g.min_size_h
        if t_min_size > h: # too high in any case
            return False
        y = 0
        for i in range(len(self.groups)-1, -1, -1):
            g = self.groups[i]
            g.compute_sizes(w)
            t_min_size_full -= g.min_size_full
            g.t_min_size_full = t_min_size_full
            t_max_size_full -= g.max_size_full
            g.t_max_size_full = t_max_size_full
            if g.t_min_size_full < g.t_min_size:
                for j in range(i):
                    dy = self.groups[j].place_stretch(y, w, self.groups[j].min_size_h)
                    y += dy
                    h -= dy
                for j in range(i+1, len(self.groups)):
                    dy = self.groups[j].place_stretch(y, w, self.groups[j].min_size_full, h) # full width
                    y += dy
                    h -= dy
                dy = g.place_stretch(y, w, h) # not full
                break
        else: # the loop was exhausted, i.e. the full width can be used. Minimize tiebreaker!
            y, t_min_size_full, t_max_size_full = 0, h, h # minimal size, min size use full width, max size using full width
            self.groups.sort(lambda g, h: cmp(h.min_size_h*h.a, g.min_size_h*g.a))
            for i in range(len(self.groups)-1, -1, -1):
                g = self.groups[i]
                g.compute_sizes(w)
                t_min_size_full -= g.min_size_full
                g.t_min_size_full = t_min_size_full
                t_max_size_full -= g.max_size_full
                g.t_max_size_full = t_max_size_full
            for i, g in enumerate(self.groups):
                if (y + g.max_size_full) < (g.t_min_size_full + g.min_size_full):
                    dy = g.place_stretch(y, w, g.max_size_full, h) # full
                    y += dy
                    h -= dy
                else:
                    h_temp = g.min_size_full + (g.t_min_size_full-y)/(len(self.groups)-i)
                    dy = g.place_stretch(y, w, h_temp, h) # full
                    y += dy
                    h -= dy

        return True

class Solution:
    """more or less a struct holding a solution"""
    def __init__(self, p):
        self.uncovered = p.w*p.h
        self.solution = []
        self.tiebreaker = 0
    def extract_solution(self, p, pics, rotated):
        areas = [q.w*q.h for q in pics]
        uncovered = p.w*p.h - sum(areas)
        tiebreaker = max(areas) - min(areas)
        if (uncovered < self.uncovered) or (uncovered == self.uncovered and tiebreaker < self.tiebreaker):
            self.uncovered = uncovered
            self.solution = [q.get_solution(rotated) for q in pics]
            self.tiebreaker = tiebreaker

def do_the_fit(page, pics, min_diff_a, solution, rotated, end_time):
    page.a = float(page.w)/float(page.h)
    p_a = page.a
    w = page.w
    num_pics = len(pics)

    c1 = time.clock()
    while 2*time.clock() - c1 < end_time:
        c1 = time.clock()
        for num_groups in range(1, num_pics+1):
            try:
                groups=Groups(num_groups, pics)

                cmp_a = min_diff_a+0.02
                groups.calculate(w)
                groups_cmp_a = abs(p_a-groups.aligned_a)
                if groups_cmp_a < cmp_a and groups_cmp_a <> min_diff_a:
                    min_diff_a = min(min_diff_a, groups_cmp_a)
                    cmp_a = min_diff_a+0.02
                    if groups.place_stretch(page):
                        solution.extract_solution(page, pics, rotated)

                iters = min(2000, num_pics*num_pics*num_groups*(num_pics+1-num_groups)) # this magic formula ensures that time is spent according to complexity. It's solidly based on nothing but good faith
                for i in range(iters):
                    g1, g2 = choice(groups.groups), choice(groups.groups) # random.sample is just too new for fred's server...
                    if len(g1.rects)>1:
                        g2.append(g1.pop_random())
                        groups.calculate(w)
                        groups_cmp_a = abs(p_a-groups.aligned_a)

                        if groups_cmp_a < cmp_a and groups_cmp_a <> min_diff_a:
                            min_diff_a = min(min_diff_a, groups_cmp_a)
                            cmp_a = min_diff_a+0.02
                            if groups.place_stretch(page):
                                solution.extract_solution(page, pics, rotated)
            except RuntimeError: # if nested too deep, try again with another number of groups
                pass
            except ValueError: # a valid solution cannot be found in this configuration
                pass
        # just in case we have enough time to try again: rotate some pic
        choice(pics).rotate()

    return min_diff_a

def main():
    # get input "rectangles"
    inrects = [string.split(l) for l in open(sys.argv[1]).readlines()]
    page = Rect(inrects.pop(0), 0)
    min_area = page.w*page.h/100

    pics = [Rect(l, min_area) for l in inrects]

    min_diff_a = 1000.0 # minimal difference so far between the aspect ratios of the page and the groups
    s = Solution(page)  # best solution so far (=none)

    # first, try unrotated
    min_diff_a = do_the_fit(page, pics, min_diff_a, s, False, MAXTIME*0.49 )

    # now rotate the page and try again
    page.w, page.h = page.h, page.w
    for r in pics:
        r.unrotate()
    min_diff_a = do_the_fit(page, pics, min_diff_a, s, True, MAXTIME*0.98) # return value not really needed

    # print solution
    s.solution.sort()
    print string.join(s.solution, "\n")

sys.setrecursionlimit(min(100,sys.getrecursionlimit()))
main()
if sys.version < '2.3':
    pass # Just once more: fred's server has really old software - but it's not HIS fault