M. 猫娘题
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

在探索一个古老的二维网格迷宫时，发现了许多被困住的猫娘。这些猫娘被一种名为"折线箭头"的魔法结界封印在网格的整数坐标点上。为了拯救她们，冒险者需要解除这些结界。

结界的规则非常奇怪：每个猫娘都面向一个特定的方向（共 $$$8$$$ 个方向）。如果一个猫娘所面对方向的射线上没有其他猫娘阻挡，她就可以被安全地移出地图（解除封印）。一旦一个猫娘被移出，她原本占据的位置就会变空，不再阻挡其他猫娘的视线。

冒险者当时救出了所有猫娘，成为了传说中的英雄。

如今，冒险者再次深入古老迷宫，发现猫娘们经过魔法强化后，每只都拥有了完整的身子！她们不再是孤零零的一个点，而是一个由多个相邻网格细胞组成的 $$$4$$$ 连通块。冒险者必须更加小心——现在任何猫娘的身子细胞都会阻挡其他猫娘的视线。

只有当一只猫娘眼睛位置发出的射线上（不含自身）没有任何其他猫娘的任何身子细胞时，她才能被安全救出。一旦救出，她整个身子的所有细胞会瞬间消失，不再阻挡任何人。

冒险者希望以字典序最小的顺序救出所有猫娘。如果存在多种可行顺序，请输出字典序最小的那个；若无法全部救出，请输出 $$$-1$$$。

有 $$$N$$$ 只猫娘。每只猫娘 $$$i$$$ 包含：

  • 眼睛位置 $$$(ex_i, ey_i)$$$
  • 面向方向 $$$d_i$$$
    • $$$0$$$ 北 (North)
    • $$$1$$$ 东北 (North-east)
    • $$$2$$$ 东 (East)
    • $$$3$$$ 东南 (South-east)
    • $$$4$$$ 南 (South)
    • $$$5$$$ 西南 (South-west)
    • $$$6$$$ 西 (West)
    • $$$7$$$ 西北 (North-west)
  • 一个连通的身子，由 $$$K_i$$$ 个互不相同的网格细胞组成（保证包含眼睛位置，且 $$$4$$$ 连通）

移除规则： 对于尚未被移除的猫娘 $$$i$$$，若从她的眼睛位置 $$$(ex_i, ey_i)$$$ 沿方向 $$$d_i$$$ 发出的无限射线（不含起点）上不存在任何其他猫娘的身子细胞，则她可以被移除。

移除后，该猫娘所有 $$$K_i$$$ 个细胞同时变空。

请判断是否能救出全部猫娘：

  1. 若能，输出字典序最小的合法移除顺序（猫娘编号 $$$1 \sim N$$$ 的排列）。
  2. 若不能，输出 $$$-1$$$。
Input

第一行包含一个正整数 $$$N$$$。 接下来为 $$$N$$$ 只猫娘的输入，每只格式如下：

  • 第一行：$$$ex_i\ ey_i\ d_i\ K_i$$$
  • 接下来 $$$K_i$$$ 行：每行两个整数 $$$x\ y$$$，表示该猫娘占据的一个细胞坐标。
Output

若无法全部移除，输出一行 $$$-1$$$。 若可行，输出一行 $$$N$$$ 个整数（$$$1 \sim N$$$ 的排列），表示按顺序移除的猫娘编号，请输出字典序最小的一种方案。

Examples
Input
2
0 0 2 1
0 0
1 0 6 2
1 0
2 0
Output
-1
Input
3
0 0 2 3
0 0
1 0
2 0
0 2 4 1
0 2
3 0 4 2
3 0
4 0
Output
3 1 2
Note
  • $$$1 \le N \le 2 \times 10^3$$$
  • $$$1 \le K_i \le 10^3$$$
  • 保证 $$$(ex_i, ey_i)$$$ 出现在该猫娘的 $$$K_i$$$ 个细胞中。
  • 该猫娘的 $$$K_i$$$ 个细胞 $$$4$$$ 连通（上下左右相邻）。
  • 所有猫娘的细胞全局不重叠（没有两个猫娘共用同一格子）。
  • $$$|x|, |y| \le 10^9$$$
  • $$$0 \le d_i \le 7$$$
  • 猫娘编号为输入顺序（$$$1 \sim N$$$）。