50190. Set Sorting and Searching

I'm a slow walker, but I never walk backwards.

Task Description

Remember that in the Hitting Set problem last week we need to sort the sets to hit according to their largest element. This task will demonstrate how to sort these sets. That is, there are $N$ different sets of positive integers, and you need to sort these $N$ sets by their largest elements in ascending order. If the largest elements of two sets are the same, then we compare the second largest elements, and so on. If all the largest elements of one set are the same as the largest elements of another set with more elements, the set with more elements is larger.

After sorting these $N$ sets, you will have to find out whether a set appears in the sorted $N$ sets. You should output the index of the set if it is in the sets, otherwise you should output $-1$. The sorted $N$ sets are indexed from $0$ to $N-1$.

Note

You will get TLE if you use time consuming sorting methods such as bubble sort. You will also get TLE if you use linear search the set to find a match. Also you should dynamically allocate memory for every set since $N$ is very large and the number of elements of some sets could be very large.

Input Format

The first line has an integer $N$, which is the number of sets.

The following $N$ lines represent $N$ sets. In each line, the first number $s$ is the size of the set, and the following $s$ numbers are the elements of the set.

Next, there is a number $M$, and the following $M$ lines are the sets you need to find. The format of the sets are the same as above.

  • $0 \lt N \leq 10000$
  • $0 \lt s \leq 1000$
  • $0 \lt M \leq 20000$

Output Format

You should output the search results in $M$ lines.

Subtasks

  • 20 points: you can use bubble sort and linear search.
  • 40 points: you can use quick sort and linear search.
  • 40 points: general cases.

Sample Input 1

4
3 12 4 3
5 12 33 56 67 3
2 1 2
3 33 67 56
3
3 3 4 12
5 23 34 43 3 4
3 56 67 33

Sample Output 1

1
-1
2

Sample Input 2

5
1 60
3 50 40 60
2 60 50
3 60 33 50
1 50
4
3 50 60 10
3 60 40 50
3 33 50 60
1 60

Sample Output 2

-1
4
3
1

Discussion