#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

There are *N* pools of oil underground, numbered 1 to *N*. Each pool of oil is at a distinct depth (completely at a higher depth or
lower depth than another pool of oil). The *i*th pool of oil spans horizontally from *L _{i}* to

*R*.

_{i}Wei Seng the oil tycoon has set up *M* oil rigs. The *i*th oil rig drills vertically downwards at point *X _{i}*.
It encounters

*K*pools of oil, numbered

_{i}*S*,

_{i1}*S*, ... ,

_{i2}*S*. For

_{iKi}*a*<

*b*, the pool of oil numbered

*S*is encountered before the pool of oil numbered

_{ia}*S*. Note that Wei Seng's oil rigs do not necessarily drill down all the way, that is, some oil rigs may stop drilling before encountering all the pools of oil it can possibly encounter.

_{ib}Wei Seng is interested in finding any possible permutation *P _{1}*,

*P*, ... ,

_{2}*P*, such that for

_{N}*i*<

*j*, the pool of oil numbered

*P*is higher (at a smaller depth) than the pool of oil numbered

_{i}*P*. Can you help him?

_{j}## Input

The first line contains a single integer *N*, the number of pools of oil.

The next *N* lines contain *L _{i}* and

*R*, the horizontal range that the

_{i}*i*th pool of oil spans.

The next line contains a single integer *M*, the number of oil rigs Wei Seng sets up.

The next *M* lines describe the pools of oil encountered by each oil rig.

The *i* line contains *X _{i}* and

*K*, the position of the

_{i}*i*th oil rig and the number of pools of oil encountered during drilling. This is followed by

*K*integers on the same line,

*S*,

_{i1}*S*, ... ,

_{i2}*S*, the pools of oil encountered, from the first pool encountered to the last.

_{iKi}Oil rigs will be provided in increasing *X _{i}* in the input.

## Output

Output any valid permutation *P _{1}*,

*P*, ... ,

_{2}*P*. It is guaranteed that at least one valid permutation exists.

_{N}## Limits

For all subtasks, 0 ≤ *L _{i}* <

*R*≤ 10

_{i}^{9}.

Subtask 1 (20%): 1 ≤ *N*, *M* ≤ 1000. Each oil rig will encounter all oil pools that it can possibly encounter.

Subtask 2 (20%): 1 ≤ *N*, *M* ≤ 1000.

Subtask 3 (20%): 1 ≤ *N*, *M* ≤ 30 000. At most 10^{6} oil pools will be encountered.

Subtask 4 (20%): 1 ≤ *N*, *M* ≤ 100 000. At most 10^{5} oil pools will be encountered.

Subtask 5 (20%): 1 ≤ *N*, *M* ≤ 100 000. At most 10^{6} oil pools will be encountered.

Subtask 6 (0%): Sample Testcases

## Sample Testcase 1

### Input

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

### Output

2 1 3 4

### Explanation

Please refer to the figure below. Another possible ordering would be 2 3 1 4.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 20 | 9 | 2s | 256MB | Minimum |

2 | 20 | 8 | 2s | 256MB | Minimum |

3 | 20 | 8 | 2s | 256MB | Minimum |

4 | 20 | 7 | 2s | 256MB | Minimum |

5 | 20 | 8 | 2s | 256MB | Minimum |

6 | 0 | 1 | 2s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o drill -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512