우랄 고속도로

새 고속도로 우랄을 건설할 계획이다. 이 도로의 내구성은 그 아래에 놓인 암석층에 따라 달라진다. 지층이란 하나의 암석으로 이루어진 지질 구조체를 말한다.

계획된 도로 아래에는 수평인 지층 $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$)를 주는데, 이는 도로 시작점에서 시추공까지의 거리와 그 시추공에서 발견된 지층 수이다. 이어서 $s_1, s_2, \ldots, s_k$가 위에서 아래로 놓인 순서대로 지층 번호를 준다. 시추공은 $x$가 증가하는 순서로 주어진다.

해가 존재함이 보장된다.

위에서 아래로 가능한 지층 순서를 나타내는 정수 $p_1, p_2, \ldots, p_n$을 출력한다. 각 번호는 정확히 한 번씩 나타나야 한다. 지층 $p_j$는 $p_1, \ldots, p_{j-1}$ 지층보다 위로 지나가거나 $p_{j+1}, \ldots, p_n$ 지층보다 아래로 지나가지 않아야 한다.

가능한 배치가 여럿이면 그중 아무거나 출력한다.

• $1 \leq n, m \leq 10^5$.
• 모든 시추공에서 발견된 지층의 총 개수는 $10^6$을 넘지 않는다.

문제의 그림은 예제에 해당한다.

예제에 대해서는 2 3 1 4도 올바른 답이다.

이 예제는 부분문제 1에 해당하지 않는다. 채점 대상이 되려면 부분문제 1만 풀더라도 예제를 통과해야 한다.