题目背景

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

题目描述

计划修建一条名为“乌拉尔”的新高速公路。高速公路的耐久性取决于其下方所分布的岩层结构。一个岩层是由同一种岩石组成的地质体。

在未来的高速公路下方共有 $n$ 层水平岩层。地质勘探确定了每一层岩层在高速公路下方的起点与终点位置。然而，这些岩层在深度方向上的顺序尚无法确定。

在高速公路沿线的若干位置进行了垂直钻探。每口钻井穿过了钻井位置下方的若干上部岩层。对于每口钻井，已知钻井从地表向下依次穿过的岩层顺序。如果某层岩石没有出现在该钻井中，说明它位于钻井的底部以下。

:::align{center} :::

你的任务是编写一个程序，根据钻探数据，确定一种可能的岩层深度顺序，使其不与已知的地质信息相矛盾。

输入格式

第一行包含一个整数 $n$ —— 岩层的数量。岩层编号为 $1$ 到 $n$，顺序任意。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$0 \leqslant l_i < r_i \leqslant 10^9$），表示第 $i$ 层岩石在高速公路下方的起点与终点距离。

接下来一行包含一个整数 $m$ —— 钻井的数量。

随后 $m$ 行描述每口钻井的勘探结果。每行格式如下：

$x\ k\ s_1\ s_2\ \ldots\ s_k$

其中：

• $x$ —— 钻井的位置（距公路起点的距离，$0 \leqslant x \leqslant 10^9$）；
• $k$ —— 该钻井中穿过的岩层数（$0 \leqslant k \leqslant n$）；
• $s_1, s_2, \ldots, s_k$ —— 钻井自上而下依次穿过的岩层编号。

钻井按 $x$ 坐标递增顺序给出。

保证至少存在一个满足条件的解。

输出格式

输出一行，包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$，表示一种可能的岩层从上到下的顺序。每个岩层编号从 $1$ 到 $n$，且在序列中恰好出现一次。

并且应满足以下条件：对于岩层编号 $p_j$，在整个区间中，它不会出现在岩层 $p_1, p_2, \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 也是正确的。

请注意，样例测试不属于子任务 1 的范围。

数据范围

本题包含五个子任务。每个子任务的测试集独立计分，只有当该组所有测试均通过时，才能获得该子任务的分数。

子任务	限制条件	分值
1	$1 \leqslant n, m \leqslant 1000$，每口钻井都穿过了其位置下方的所有岩层	20
2	$1 \leqslant n, m \leqslant 1000$
3	$1 \leqslant n, m \leqslant 30\,000$，钻井中岩层编号的总数不超过 $10^6$
4	$1 \leqslant n, m \leqslant 10^5$，钻井中岩层编号的总数不超过 $10^5$
5	$1 \leqslant n, m \leqslant 10^5$，钻井中岩层编号的总数不超过 $10^6$