Ural Highway

A new highway named Ural is planned. Its durability depends on the rock layers beneath it. A stratum is a geological body made of a single rock.

$n$ horizontal strata lie under the planned highway. A geological survey found the points along the highway where each stratum begins and ends. The depth order of the strata could not be determined.

Vertical boreholes were drilled at set points along the highway. Each borehole passes through several of the upper strata beneath its point. For each borehole, the order of the drilled strata from the surface downward is known. If a borehole does not reach a stratum that lies beneath its point, that stratum runs below the bottom of the borehole.

Write a program that finds a possible depth order of the strata that agrees with the data.

The first line contains an integer $n$, the number of strata. The strata are numbered from $1$ to $n$ in arbitrary order. Each of the next $n$ lines contains integers $l_i$ and $r_i$ ($0 \leq l_i < r_i \leq 10^9$), the distances from the start of the highway to the points where the $i$-th stratum begins and ends.

The next line contains an integer $m$, the number of boreholes. Each of the next $m$ lines describes one borehole. It starts with two integers $x$ ($0 \leq x \leq 10^9$) and $k$ ($0 \leq k \leq n$), the distance from the start of the highway to the borehole and the number of strata found in it. It is followed by $s_1, s_2, \ldots, s_k$, the stratum numbers in order from top to bottom. The boreholes are listed in increasing order of $x$.

It is guaranteed that a solution exists.

Print $n$ integers $p_1, p_2, \ldots, p_n$, the possible depth order of the strata from top to bottom. Each stratum number must appear exactly once. Stratum $p_j$ must never pass above strata $p_1, \ldots, p_{j-1}$ or below strata $p_{j+1}, \ldots, p_n$.

If several arrangements are possible, print any of them.

• $1 \leq n, m \leq 10^5$.
• The total number of strata found across all boreholes does not exceed $10^6$.

The figure in the statement matches the example.

For the example, the answer 2 3 1 4 is also correct.

The example test does not belong to subtask 1. To be accepted for judging, a solution must pass the example even if it solves only this subtask.