In the same sentence

searching intersections binary search search engines classic

War and Peace has 31,252 sentences. A search over the novel must answer questions like “in how many sentences do «бал» (“ball”) and «Наташа» occur together”. For each word a posting list is already ready: the numbers of the sentences it occurs in, in increasing order. The lists are stored, as in real search indexes, as differences: the first number is the number of the first sentence, and each next one is how much the number is greater than the previous. For example, sentences 2, 5 and 10 are written as “2 3 5”.

For each query of several words, print how many sentences contain all its words.

Input

The first line holds the number of words n (1 ≤ n ≤ 5000). Then come n lines: a word, the length of its list m (m ≥ 1) and the m numbers of the list as differences. The words are distinct, consist of lowercase Cyrillic or Latin letters and digits, and are up to 20 characters long. Sentence numbers are from 1 to 10⁶, and the sum of all m is at most 3·10⁵.

Then the number of queries q (1 ≤ q ≤ 6·10⁴) and q lines: the number of words in the query k (2 ≤ k ≤ 4) and the words themselves, distinct, each among the n. If for each query you take the length of the shortest of its lists, the sum of these lengths over all queries is at most 10⁶.

Output

q lines: for each query, the number of sentences containing all its words.

The second example is the lists of six words over the first 60 sentences of the novel.

Examples

Example 1

Input

4
бал 3 2 3 5
и 6 1 1 2 2 4 1
наташа 3 2 4 4
не 4 3 1 4 2
3
2 бал и
3 наташа и бал
3 не бал наташа

Output

2
2
1

Example 2

Input

6
и 22 5 1 3 1 1 1 9 2 4 1 1 3 3 2 3 5 1 2 1 1 1 9
не 14 9 1 2 11 5 1 2 1 5 3 5 3 1 1
князь 6 9 11 3 2 1 28
анна 5 6 1 9 11 3
павловна 5 6 1 9 11 3
он 6 10 1 1 11 14 15
4
2 анна павловна
3 князь и он
4 он не и князь
2 павловна не

Output

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 7 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

«бал» is in 18 sentences, «и» (“and”) in 13,480. How many of these 13,480 numbers do you need to see to check eighteen?

2The idea

Convert the lists once from differences into numbers, with running sums. Then start each query with the shortest list: its numbers are the candidates, and each next list can only weed them out. Look for a candidate in a long list not step by step but by binary search. The candidates go in increasing order, so the search for the next starts where the previous stopped: the long list is never read in full. Each pair of lists takes O(m · log n) instead of m + n, where m is the length of the short one and n of the long one.

3Walkthrough

In Python this is bisect_left(b, x, lo) with a growing lower bound lo. In Go, the galloping from the article: from the current position jumps of 1, 2, 4, 8… forward until the candidate is overshot, then a binary search inside the last jump. If the candidate is d places away, galloping looks at about 2·log₂ d numbers, and the whole pair takes O(m · log(n/m)). When the candidates run out, the other lists of the query need not be touched.

Another way also works: build a set for each list once in advance and check the candidates in it, O(m) per query, but the hash tables take several times more memory than the lists themselves. Two fingers, however, as in chapter 48 of the course, do not make it in time here, though they give the right answer. They go through the long list almost entirely: in the third test that is 196 million steps, although the sum of the lengths of the shortest lists is 688 thousand, in the fourth 433 million. In the last test the long list is 200,000 consecutive sentences, and the fingers would have to make about ten billion steps.

3+Solution

4Complexity

Converting from differences is O(sum of m). A query is O(m · k · log n), where m is the length of its shortest list; with galloping, O(m · k · log(n/m)).

5Common mistakes

Two fingers. O(m + n) per pair: the long list is read from start to end on every query.
Not starting from the shortest. If the candidates are a long list, there are thousands of them, and each is searched for in the others.
A set per query. set(long) inside a query is the same pass over the long list, just hidden.
Forgetting the differences. The numbers in the input are gaps between sentence numbers, not the numbers themselves.

Algorithms behind it

SYS Data structure Inverted index and BM25 A dictionary “word → documents that contain it”: a query reads a few short lists instead of all the texts. O(total length of the query words' lists); AND by galloping O(m·log(n/m)) 2 problems SRT Algorithm Binary search Finds the “no → yes” boundary in ordered data in log₂ n checks. O(log n) 2 problems