IOI '97 - Cape Town, South Africa

You are a cartographer's assistant, and have been given the difficult task of writing the names of cities onto a new map.

The map is a grid of $1000\times 1000$ cells. Grid cells coordinates are labelled from $0$ to $999$ inclusive in the horizontal and vertical direction respectively. Each city occupies a single cell on the map. City names are to be placed on the map in rectangular boxes of cells. Such boxes are called labels.

Figure 1: a city with the four possible positions of its label

The placement of labels must satisfy the following constraints:

1. A city's label must appear in one of four positions with respect to the city as illustrated in figure $1$.
2. Labels must not overlap each other.
3. Labels must not overlap cities.
4. Labels must completely fit on the map.

Each label contains all the letters in a city name plus a single space. For each city name the width and height of its letters will be given; the single space has the same size.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	$\dots$
0	_	C	e	r	e	s
1							O		P	a	a	r	l	_
2
3	O							O
4		L	a	n	g	a	_
$⋮$
_ represents a space O represents the position of a city

Figure 2: a section of a labelled map

The leftmost column of the map has horizontal index 0 and the top row has vertical index $0$. Figure $2$ shows the top left section of a map for the cities Langa at $(0,3)$, Ceres at $(6,1)$ and Paarl at $(7,3)$. All the labels are validly placed, but this is not the only valid placement.

Your program must read the locations of the cities on the map, followed by their letter dimensions and names. The program must then place as many labels on the map as it can without violating the constraints above, and output the locations of the labels that have been placed.

Input Specification

The input starts with a line containing an integer $N$ giving the number of cities on the map. For each city there is an input line with

• the city's horizontal index $X$,
• the city's vertical index $Y$,
• the integer width $W$ for each character of the city name,
• the integer height $H$ for each character of the city name, and
• the city name itself, which consists only of uppercase and lowercase characters from A to Z.

City names are all single words. The number of cities is at most $1000$. No city name will be longer than $200$ letters.

Output Specification

Your program must output $N$ lines. Each line must contain the horizontal index followed by the vertical index of the top left cell of the city's label, separated by a single space. If your program is unable to place a label for a city, it must output -1 -1 for that city. These lines should be printed in the same order as the cities are given in the input.

Sample Input

3
0 3 1 1 Langa
6 1 1 1 Ceres
7 3 1 2 Paarl

N = 3
X = 0, Y = 3, W = 1, H = 1
X = 6, Y = 1, W = 1, H = 1
X = 7, Y = 3, W = 1, H = 2

Sample Output

1 4
0 0
8 1

Langa's label is at (1,4)
Ceres's label is at (0,0)
Paarl's label is at (8,1)

Scoring

For each test case:

• Your score will be given as the percentage of city names placed by your program with respect to an excellent solution of the IOI organisers, rounded to the nearest integer percent.
• The minimum score is $0\mathrm{\%}$ and the maximum score is $100\mathrm{\%}$.
• If any label violates the constraints, your program will score $0$.
• If labels do not match the cities given, your program will score $0$.