题目描述

译自 ROI 2014 Day2 T4. Магистраль «Урал»

计划建设一条新的乌拉尔高速公路。高速公路的耐久性取决于其下方的岩层结构。岩层是指由单一岩石类型构成的地质体。

在未来高速公路下方有 $n$ 个水平岩层。地质勘探已确定了每个岩层在高速公路下方起始和结束的位置。然而，岩层在深度上的排列顺序尚未确定。

在规划的高速公路沿线特定位置钻探了垂直井孔。每个井孔穿透了钻探点下方的若干上层岩层。对于每个井孔，已知其穿透的岩层从地表向下排列的顺序。如果某个井孔未穿透钻探点下方的某个岩层，则说明该岩层位于井孔底部之下。

你需要编写一个程序，确定一个与勘探数据不矛盾的岩层深度排列顺序。

输入格式

输入文件的第一行包含一个整数 $n$，表示岩层的数量。岩层编号为从 $1$ 到 $n$ 的整数，顺序任意。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$ $(0 \leq l_i < r_i \leq 10^{9})$，分别表示第 $i$ 个岩层在高速公路下方起始和结束的距离。

接下来的一行包含一个整数 $m$，表示钻探井孔的数量。

随后的 $m$ 行描述钻探结果：每行首先有两个整数 $x$ $(0 \leq x \leq 10^{9})$ 和 $k$ $(0 \leq k \leq n)$，分别表示井孔距高速公路起点的距离和该井孔发现的岩层数量；然后是 $k$ 个整数 $s_1, s_2, \ldots, s_k$，表示井孔穿透的岩层编号，按从上到下的顺序排列。井孔按距离 $x$ 升序排列。

保证存在至少一种解法。

输出格式

输出文件的第一行应包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$，表示从上到下的一种可能的岩层排列顺序。数字 $p_1, p_2, \ldots, p_n$ 中每个岩层编号必须且仅出现一次，且岩层编号 $p_j$ 在任何位置不得位于编号 $p_1, \ldots, p_{j-1}$ 的岩层之上或编号 $p_{j+1}, \ldots, p_n$ 的岩层之下。

如果存在多种可能的排列顺序，可以输出任意一种。

4
1 5
2 7
7 10
1 11
3
1 1 1
4 1 2
7 2 2 3

2 1 3 4

条件中的图示对应样例内容。

对于给出的样例，答案 2 3 1 4 也是正确的。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。