The best paragraphs

ranking searching heap search engines in production

Build a search over paragraphs, made the same way as in search libraries. The paragraphs are already split into words: lowercase Latin letters, no punctuation. A query is one, two or three words. A query gives each paragraph D a BM25 score:

$$\text{score}(D) = \sum_{w} \text{idf}(w) \cdot \frac{\text{tf} \cdot (k_1 + 1)}{\text{tf} + k_1 \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)},$$

$$\text{idf}(w) = \ln\left(1 + \frac{N - \text{df} + 0.5}{\text{df} + 0.5}\right),$$

where the sum is over the query words that occur in D; tf is how many times w occurs in D, |D| the number of words in D, avgdl the mean number of words per paragraph, N the number of paragraphs, df how many paragraphs contain w; k₁ = 1.2, b = 0.75. For each query print the k paragraphs with the highest score. Paragraphs that contain no query word do not get into the answer. Among the tests are the paragraphs of War and Peace in the translation by Louise and Aylmer Maude.

Input

The first line holds N and k (1 ≤ N ≤ 4·10⁴, 1 ≤ k ≤ 10). Then come N lines, the paragraphs: words separated by spaces, at least one word in each, up to 20 letters long; at most 3·10⁵ words in all the paragraphs together.

Then the number of queries q (1 ≤ q ≤ 3·10⁴) and q lines: the number of words in the query c (1 ≤ c ≤ 3) and the words themselves, distinct. If for each word of each query you take how many paragraphs it occurs in, the sum of these numbers is at most 2·10⁶.

Output

For each query, a line with paragraph numbers (from one) in decreasing order of score, at most k numbers. In the tests the first k scores of a query and the one after them differ from each other by more than 10⁻⁶, so the order is unambiguous. If no paragraph contains any query word, print 0.

The second example is six short consecutive paragraphs of the novel.

Examples

Example 1

Input

6 2
natasha went to the ball
the ball was the first ball in her life
pierre did not dance
natasha and pierre talked about the war
the old prince did not go to the ball at all
war and peace
4
2 natasha ball
1 the
2 war pierre
1 hunt

Output

Example 2

Input

6 3
i don t understand mamma what is his attitude to pierre asked the son
the will will show that my dear our fate also depends on it
but why do you expect that he will leave us anything
ah my dear he is so rich and we are so poor
well that is hardly a sufficient reason mamma
oh heaven how ill he is exclaimed the mother
3
1 pierre
2 my dear
3 what is it

Output

1
4 2
1 2 5

Limits

Time · Python: 6000 ms
Time · Go: 1500 ms
Memory: 256 MB
Judging: 6 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

The last test has 40,000 paragraphs and 30,000 queries. How many paragraphs can actually get any score for a query of two rare words?

2The idea

The score is made up only of the query words present in the paragraph. A paragraph without them gets zero, and there is no point looking at it. So you need an inverted index: for each word, a list of “paragraph, how many times” pairs. It is built once, in a pass over all the paragraphs, remembering the length of each paragraph along the way. A query goes only through the lists of its words and accumulates scores in a dictionary “paragraph → sum”: this is the term-at-a-time order. It remains to choose the k best of the paragraphs touched.

3Walkthrough

The BM25 denominator depends on the paragraph but not on the query: k₁ · (1 − b + b · |D| / avgdl) is conveniently precomputed for each paragraph. idf is computed from the length of the word’s list, which is exactly df. The k best: heapq.nlargest in Python or sorting the touched ones in Go: there are usually few. The work per query is proportional to the total length of its words’ lists. Going over all paragraphs for each query gives the same answer, but in the last test that is more than a billion checks.

The idf formula in the statement has a one under the logarithm, as in Lucene. In the original formula of Robertson and Spärck Jones there is no one, and a word that occurs in more than half the paragraphs has a negative idf: “the” in the fourth test is in 2046 paragraphs of 3000, and a paragraph with “the” would lose points. This is no trifle: with that formula 1072 answers of 4000 in the fourth test would differ, and even 320 of 20,000 in the third, which has no frequent words: the ratios of the weights change there.

3+Solution

4Complexity

The index is O(total words). A query is O(S + T log k), where S is the total length of its words’ lists and T ≤ S the number of paragraphs touched.

5Common mistakes

Going over all paragraphs for each query. The formula is right and so is the answer, but the work is O(N) per query instead of the length of the lists.
idf without the one. Frequent words get a negative weight, and the order changes.
The paragraph length as the number of distinct words. |D| is all the words with repeats, as is avgdl.
Paragraphs with a zero score. If fewer than k paragraphs match, print as many as there are, without padding with zeros.

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