SP210 ALTARS - The Altars

根据中国的民间信仰，邪灵只能沿着直线移动，这一点在建造寺庙时非常重要。寺庙位于矩形的平面上，其边缘与南北或东西方向平行。任意两个矩形之间没有公共点。寺庙的入口位于四面墙之一的中间，入口宽度是该墙长度的一半。祭坛位于寺庙的中心，即矩形对角线的交点。如果有邪灵出现在这个位置，寺庙将会被玷污。只有在可以从祭坛通过入口画一条射线，该射线延伸至无穷远且不与任何寺庙的墙壁交叉或接触时，这种情况才可能发生。这意味着可以在建筑区域上画出一条从祭坛起始，通向无穷远且不触碰任何墙的直线。 ### 任务 请编写一个程序，完成以下功能： - 读取输入，获取寺庙的描述信息； - 判断哪些寺庙会被可能被玷污； - 输出这些寺庙的编号。

第一行输入一个整数 $t$，表示测试用例的数量。接下来有 $t$ 组测试用例，每组用例之间用空行隔开。在每一组测试用例的第一行有一个整数 $n$，表示寺庙的数量，满足 $1 \le n \le 1000$。 接下来的 $n$ 行中，每行给出一个寺庙的描述（第 $i$ 行描述第 $i$ 座寺庙）。每个寺庙的描述包括四个非负整数和一个字母 E、W、S 或 N。前两个整数表示寺庙西北角的坐标，后两个整数表示东南角的坐标。坐标的表示形式是先经度（东西方向，数值从西向东递增），后纬度（南北方向，数值从南向北递增）。第五个字母表示带有入口的墙（E 表示东墙，W 表示西墙，S 表示南墙，N 表示北墙）。描述中的各个元素以单个空格分隔。

对于每个测试用例，依次输出可能被邪灵玷污的寺庙编号，按照升序排列，每个编号占一行。如果没有这样的寺庙，输出单词 `NONE`。 **本翻译由 AI 自动生成**