题干：

Professor Clumsey is going to give an important talk this afternoon. Unfortunately, he is not a very tidy person and has put all his transparencies on one big heap. Before giving the talk, he has to sort the slides. Being a kind of minimalist, he wants to do this with the minimum amount of work possible. 

The situation is like this. The slides all have numbers written on them according to their order in the talk. Since the slides lie on each other and are transparent, one cannot see on which slide each number is written. 


Well, one cannot see on which slide a number is written, but one may deduce which numbers are written on which slides. If we label the slides which characters A, B, C, ... as in the figure above, it is obvious that D has number 3, B has number 1, C number 2 and A number 4. 

Your task, should you choose to accept it, is to write a program that automates this process.

Input

The input consists of several heap descriptions. Each heap descriptions starts with a line containing a single integer n, the number of slides in the heap. The following n lines contain four integers xmin, xmax, ymin and ymax, each, the bounding coordinates of the slides. The slides will be labeled as A, B, C, ... in the order of the input. 

This is followed by n lines containing two integers each, the x- and y-coordinates of the n numbers printed on the slides. The first coordinate pair will be for number 1, the next pair for 2, etc. No number will lie on a slide boundary. 

The input is terminated by a heap description starting with n = 0, which should not be processed. 

Output

For each heap description in the input first output its number. Then print a series of all the slides whose numbers can be uniquely determined from the input. Order the pairs by their letter identifier. 

If no matchings can be determined from the input, just print the word none on a line by itself. 

Output a blank line after each test case. 

Sample Input

4
6 22 10 20
4 18 6 16
8 20 2 18
10 24 4 8
9 15
19 17
11 7
21 11
2
0 2 0 2
0 2 0 2
1 1
1 1
0

Sample Output

Heap 1
(A,4) (B,1) (C,2) (D,3)

Heap 2
none

题目大意：

给出一些重叠的矩形，按照给出的顺序分别编号为A、B、C，对于每个矩形给出左下角和右上角的xy坐标（注意读入顺序）。然后再给出一些点，这些点画在了某个矩形上，根据给出的顺序分别编号为1,2,3，对于每个点给出其xy坐标。矩形是透明的所以一次就可以看到所有的点和所有矩形的外轮廓，问能否确定某个点一定在某个矩形上（每个矩形上都有且只有一个点）。

如果可以确定一对编号，则以成对形式输出确定对应的纸编号和数字（也就是说不一定输出n对）。如果一个确定的对应都没有，则输出none。

解题报告：

不难看出是个二分图模型，首先判断是否可以完全匹配，在此基础上看能否一一对应。也就是说满足none的情况有两种，要么是匹配数都不是n，要么是一个必须边都没有。

当然这题这么做复杂度还有有点高，在判断必须边的时候是n^2枚举的然后再跑匈牙利，复杂度就有点高，其实可以换种思考方式，如果他是必须边，那就只可能是你第一次求出的nxt数组中匹配到的值，所以我们可以建边的时候不是f[j][i]=1，而是f[i][j]=1，然后求出一组nxt赋值给xM数组，这样枚举第二维，直接调用xM[i]就可以求出对应的左侧的二分图中的值（第一维），那么直接操作的边就是f[xM[i]][i]，如果去掉这个边之后match()变了，那么这一定就是必须边了，直接输出 i+'A'-1 , xM[i]就行，因为你是枚举的第二维，而建边的时候正好就是第二维是纸张（用ABCD表示的那个而非1234表示的那个）而题目要求正好是优先字母的字典序升序，所以正好可以堆起来了。（相应的代码是AC代码2）

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 555 + 5;
bool used[MAX];
int nxt[MAX],n,f[MAX][MAX];
bool find(int x) {
	for(int i = 1; i<=n; i++) {
		if(used[i] == 0 && f[x][i]) {
			used[i] = 1;
			if(nxt[i] == 0|| find(nxt[i])) {
				nxt[i] = x;
				return 1;
			} 
		}
	}
	return 0 ;
}
int match() {
	memset(nxt,0,sizeof nxt);
	int res = 0;
	for(int i = 1; i<=n; i++) {
		memset(used,0,sizeof used);
		if(find(i)) res++;
	}
	return res;
}
struct Node {
	int x1,x2,y1,y2;
} nn[MAX];
int x[MAX],y[MAX];
int main()
{
	int iCase = 0;
	while(~scanf("%d",&n) && n) {
		memset(f,0,sizeof f);
		memset(nxt,0,sizeof nxt);
		if(iCase!=0) puts("");
		printf("Heap %d\n",++iCase);
		for(int i = 1; i<=n; i++) {
			scanf("%d%d%d%d",&nn[i].x1,&nn[i].x2,&nn[i].y1,&nn[i].y2);
		}
		for(int i = 1; i<=n; i++) {
			scanf("%d%d",x+i,y+i);
			for(int j = 1; j<=n; j++) {
				if(x[i]>=nn[j].x1&&x[i]<=nn[j].x2&&y[i]>=nn[j].y1&&y[i]<=nn[j].y2) 
					f[j][i] = 1;
			}
		}
		int ans = match(),cnt = 0; 
		if(ans != n) {puts("none");continue;	}
		for(int i = 1; i<=n; i++) {
			for(int j = 1; j<=n; j++) {
				if(f[i][j] == 0) continue;
				f[i][j] = 0;
				if(match() != n) {
					if(cnt) printf(" "); 
					printf("(%c,%d)",i+'A'-1,j);
					cnt++;
				}
				f[i][j] = 1;
			}
		}
		if(cnt == 0) puts("none"); 
		else puts("");
	}


	return 0 ;
}

AC代码2：链接

#include<stdio.h>
#include<string.h>
#include<iostream>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int> P;
const int MAXN = 30;
int uN, vN;
int g[MAXN][MAXN], linker[MAXN], tmp[MAXN];
bool used[MAXN];
bool dfs(int u)
{
	for(int v = 0; v < vN; v++)
	if(g[u][v] && !used[v])
	{
		used[v] = 1;
		if(linker[v] == -1 || dfs(linker[v]))
		{
			linker[v] = u; return 1;
		}
	}
	return 0;
}
int hungary()
{
	int res = 0;
	memset(linker, -1, sizeof(linker));
	for(int u = 0; u < uN; u++)
	{
		memset(used, 0, sizeof used);
		if(dfs(u)) res++;
	}
	return res;
}
struct node{
	int x1, x2, y1, y2;
}p[30];
bool inside(P &u, node &v)
{
	if(u.first > v.x1 && u.first < v.x2 && u.second > v.y1 && u.second < v.y2) return true;
	return false;
}
int main()
{
	int Heap = 1;
	while(scanf("%d", &uN), uN)
	{
		memset(g, 0, sizeof g);
		vN = uN;
		for(int i = 0; i < uN; i++)
		scanf("%d %d %d %d", &p[i].x1, &p[i].x2, &p[i].y1, &p[i].y2);
		P t;
		for(int i = 0; i < uN; i++)
		{
			scanf("%d %d", &t.first, &t.second);
			for(int j = 0; j < uN; j++)
			if(inside(t, p[j]))
			g[i][j] = 1;
		}
		printf("Heap %d\n", Heap++);
		int ans = hungary();
		if(ans != vN)
		{
			puts("none\n");
			continue;
		}
		bool flag = 0;
		memcpy(tmp, linker, sizeof(tmp));
		for(int i = 0; i < vN; i++)
		{
			g[tmp[i]][i] = 0;
			if(ans != hungary())
			{
				printf("(%c,%d) ", 'A' + i, tmp[i] + 1);
				flag = 1;
			}
			g[tmp[i]][i] = 1;
		}
		if(!flag) puts("none\n");
		else
		puts("\n");
	}
 	return 0;
}