Map Labelling

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 x 1000 cells. 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.

Fig. 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.

4

L

a

n

g

a

_

3

O

O

2

P

a

a

r

l

_

1

O

0

_

C

e

r

e

s

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

 

_ represents a space

O represents the position of a city

Fig. 2: Section of a map

The leftmost column of the map has horizontal index 0 and the bottom row has vertical index 0. Figure 2 shows the bottom 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.

Task:

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:

The input file 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 in the city name,
  • the integer height (H) for each character in the city name, and
  • the city name itself.

City names are all single words. The number of cities is at most 1000.

No city name will be longer than 200 letters.

Sample input:

MAPS.DAT

Explanation

3

N=3

0 3 1 1 Langa

X=0, Y=3, W=1, H=1

6 1 1 1 Ceres

 

7 3 1 2 Paarl

 

Output:

Your program is required to 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. If your program is unable to place a label for a city, it must output -1 -1. These lines should be output in the same order as the cities are given in the input file. You must put a single space between the two numbers.

Sample output:

MAPS.OUT

Explanation:

1 4

Langa's label is at (1,4)

0 0

Ceres's label is at (0, 0)

8 2

Paarl's label is at (8, 2)

Scoring:

For each set of the test data:

  • The score will be given as the percentage of city names placed by your program with respect to an excellent solution of the organisers.
  • The minimum score is 0% and the maximum score is 100%.
  • If any label violates the constraints, your program will score 0.
  • If labels do not match the cities given, your program will score 0.