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 ith pool of oil spans horizontally from Li to Ri.
Wei Seng the oil tycoon has set up M oil rigs. The ith oil rig drills vertically downwards at point Xi.
It encounters Ki pools of oil, numbered Si1, Si2, ... ,
SiKi. For a < b, the pool of oil numbered Sia is
encountered before the pool of oil numbered Sib. 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.
Wei Seng is interested in finding any possible permutation P1, P2, ... , PN, such that
for i < j, the pool of oil numbered Pi is higher (at a smaller depth) than the pool of oil numbered
Pj. Can you help him?
The first line contains a single integer N, the number of pools of oil.
The next N lines contain Li and Ri, the horizontal range that the ith 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 Xi and Ki, the position of the ith oil rig and the number of pools of oil
encountered during drilling. This is followed by K integers on the same line, Si1, Si2, ... ,
SiKi, the pools of oil encountered, from the first pool encountered to the last.
Oil rigs will be provided in increasing Xi in the input.
Output any valid permutation P1, P2, ... , PN. It is guaranteed that at least one valid permutation
For all subtasks, 0 ≤ Li < Ri ≤ 109.
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 106 oil pools will be encountered.
Subtask 4 (20%): 1 ≤ N, M ≤ 100 000. At most 105 oil pools will be encountered.
Subtask 5 (20%): 1 ≤ N, M ≤ 100 000. At most 106 oil pools will be encountered.
Subtask 6 (0%): Sample Testcases
Sample Testcase 1
1 1 1
4 1 2
7 2 2 3
2 1 3 4
Please refer to the figure below. Another possible ordering would be 2 3 1 4.