oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

drill Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

drill.html

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 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?

Input

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

Output any valid permutation P1, P2, ... , PN. It is guaranteed that at least one valid permutation exists.

Limits

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

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.

drill.png

Tags

ROI 2014

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
12092s256MBMinimum
22082s256MBMinimum
32082s256MBMinimum
42072s256MBMinimum
52082s256MBMinimum
6012s256MBMinimum

Judge Compile Command

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

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.