Big File System Search
You have recently got a job as a system administrator in a big IT company.
The first problem which you encountered is to build a data structure which allows you to do some array-oriented searching in a big file system.
You have files in your system. Each file is represented by a sequence of integers separated by a single space.
You have to perform queries. For each query, you will be given an array , and you have to perform any one of the following three queries on the whole file system:
- : Returns the number of files which contain all elements from array .
- : Returns the number files which contain at least one element from array .
- : Returns the number of files which contain at least one element and at most elements from array .
Note: A array, , will be considered to contain all elements of another array, , if and only if the frequency of each element of doesn't exceed the respective frequency in array . That is, if and then doesn't consists all elements of , as frequency of in is greater than .
Input Format
In the first line there is only one integer, , denoting the number of files in the file system.
lines follow. In the of them there is a description of the file. Each such description consists of a number, , denoting the number of integers in this file, followed by integers representing these integers.
The next line consists of a single integer, , denoting the number of queries which you have to perform.
lines follow. In the of them there is a description of the query. Each query consists of an integer, , denoting the type of the query followed by an integer, , denoting the length of array . Then follows integers, in the same line, representing the elements of .
Output Format
Print exactly lines. In the of them print the answer to the query.
Constraints:
- All numbers in the files and queries are greater than and not greater than .
Sample Input
3
3 1 2 3
3 2 3 4
3 3 4 5
3
1 2 3 4
2 2 2 5
3 3 2 3 4
Sample Output
2
3
2
Explanation
There are three queries:
You have to count the number of files which contain numbers and . The second and the third file is valid for this query, so the answer is .
You have to count the number of files which contain number or number . All files are valid for this query, so the answer is .
You have to count the number of files which contain some numbers from the array , but not all of them. The first and the third file is valid for this query, so the answer is .
Tested by: Ray Williams Robinson Valiente