1. 

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 663 Sorting Slides
* Link: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=604
*
* @author Fabian Liebl
* @version 1.0, 10/06/2010
*
* Method : Bipartite matching
* Status : Accepted
* Runtime: 0.256
*/

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Main {

private static int s,t; // Start and target node
private static int[][] C; // Capacities
private static ArrayList<LinkedList<Integer>> E; // Neighbours
private static int[][] F; // Flow matrix

// For Breadth-First-Search
private static int[] M;
private static int[] P;

private static void breadthFirstSearch() {
int u;

LinkedList<Integer> queue = new LinkedList<Integer>();

Arrays.fill(P, -1);
P[s] = -2; // No backjumping to source
M[s] = Integer.MAX_VALUE;
queue.clear();
queue.addLast(s);
while (queue.size() > 0) {
u = queue.removeFirst();
for (int v: E.get(u)) {
if ((C[u][v] - F[u][v] > 0) && (P[v] == -1)) {
P[v] = u;
M[v] = Math.min(M[u], C[u][v] - F[u][v]);
if (v == t) {
return;
} else {
queue.addLast(v);
}
}
}
}
// No path found
M[t] = 0;
}

public static void print2dArray(int[][] array) {
for (int i = 0; i < array.length; i++) {
System.out.println("[" + Arrays.toString(array[i]) + "]");
}
}

public static void main(String[] args) throws IOException {
BufferedReader inputReader = new BufferedReader(new InputStreamReader(System.in));

int sheets = Integer.parseInt(inputReader.readLine());
int[] sheetx1;
int[] sheety1;
int[] sheetx2;
int[] sheety2;

int[] numberx;
int[] numbery;

int f, maxf; // Flow value
int v,u; // Indices

int[] solution;

E = new ArrayList<LinkedList<Integer>>();

String[] line;

int tc = 1;

while (sheets > 0) {
sheetx1 = new int[sheets];
sheety1 = new int[sheets];
sheetx2 = new int[sheets];
sheety2 = new int[sheets];
numberx = new int[sheets];
numbery = new int[sheets];
C = new int[2*sheets + 2][2*sheets + 2];
E.clear();
for (int i = 0; i < 2*sheets + 2; i++) {
E.add(new LinkedList<Integer>());
}
F = new int[2*sheets + 2][2*sheets + 2];
s = 2*sheets;
t = 2*sheets + 1;
M = new int[2*sheets + 2];
P = new int[2*sheets + 2];
solution = new int[sheets];
for (int i = 0; i < sheets; i++) {
line = inputReader.readLine().split(" ");
sheetx1[i] = Integer.parseInt(line[0]);
sheetx2[i] = Integer.parseInt(line[1]);
sheety1[i] = Integer.parseInt(line[2]);
sheety2[i] = Integer.parseInt(line[3]);
}
for (int i = 0; i < sheets; i++) {
line = inputReader.readLine().split(" ");
numberx[i] = Integer.parseInt(line[0]);
numbery[i] = Integer.parseInt(line[1]);
}

for (int i = 0; i < sheets; i++) {
E.get(i).add(s);
E.get(s).add(i);
C[s][i] = 1;
E.get(sheets + i).add(t);
E.get(t).add(sheets + i);
C[sheets + i][t] = 1;
for (int j = 0; j < sheets; j++) {
if ((numberx[j] > sheetx1[i]) && (numberx[j] < sheetx2[i])
&& (numbery[j] > sheety1[i]) && (numbery[j] < sheety2[i])) {
E.get(i).add(sheets + j);
E.get(sheets + j).add(i);
C[i][sheets + j] = 1;
}
}
}

// Do first (maximal) solution
f = 0;

while (true) {
// Find path through breadth first search
breadthFirstSearch();

if (M[t] == 0) {
break;
}
f += M[t];
// Path is in P (backwards)
v = t;
while (v != s) {
u = P[v];
// Add flow
F[u][v] += M[t];
// Add negative flow in the other direction
F[v][u] -= M[t];
v = u;
}
}

maxf = f;

if (f == 0) {
// No possible solution
Arrays.fill(solution, -1);
} else {
// Parse solution
for (int i = 0; i < sheets; i++) {
for (int j = sheets; j < 2*sheets; j++) {
if (F[i][j] == 1) {
solution[i] = j;
break;
}
}
}
// Remove solution for every sheet and test if the flow gets less
for (int i = 0; i < sheets; i++) {
// Remove edge of this solution
E.get(i).remove(new Integer(solution[i]));
E.get(solution[i]).remove(new Integer(i));
f = 0;
for (int j = 0; j < 2*sheets + 2; j++) {
Arrays.fill(F[j], 0);
}

while (true) {
// Find path through breadth first search
breadthFirstSearch();

if (M[t] == 0) {
break;
}
f += M[t];
// Path is in P (backwards)
v = t;
while (v != s) {
u = P[v];
// Add flow
F[u][v] += M[t];
// Add negative flow in the other direction
F[v][u] -= M[t];
v = u;
}
}

// Add removed edge
E.get(i).add(new Integer(solution[i]));
E.get(solution[i]).add(new Integer(i));

if (f == maxf) {
// Solution not unique
solution[i] = -1;
}
}
}


boolean found = false;
boolean first = true;
System.out.printf("Heap %d\n", tc++);
char c = 'A';
for (int i = 0; i < sheets; i++) {
if (solution[i] > -1) {
if (!first) {
System.out.print(" ");
}
System.out.printf("(%c,%d)", c + i, solution[i] - sheets + 1);
found = true;
first = false;
}
}
if (!found) {
System.out.println("none");
} else {
System.out.println();
}
System.out.println();

sheets = Integer.parseInt(inputReader.readLine());
}
}

}