Trending Topic

Time limit1sMemory limit128 MB

Summary

Maintain word counts over a rolling 7-day window and answer each top N query in frequency order with ties included.

Level: Medium5 of 10
Topics: Sliding window, Hash map, Sorting
Solved: No attempts yet

Problem

A company that analyzes text on the web is hiring, and one of its tests asks you to write a program that keeps a set of trending topics up to date. Whether you get the job depends on how efficient your program is.

The company hands you text collected from the most active blogs, grouped one batch per day. When a query arrives, report the $N$ most frequent words over the last 7 days of text, counting the day that just ended.

Input

Each input file holds one test case. The text for a single day sits between a <text> line and a </text> line.

A query for the top $N$ words can appear between the texts of two different days, written as a tag like <top 10 />. The number is always surrounded by whitespace, so a query reads as three whitespace separated tokens: <top, the number, then />.

Input ends at end of file.

Output

Answer every query in the order it appears. For a query <top N />, print a line <top N>, then one line per reported word in the form word count, then a line </top>.

Sort words by decreasing number of appearances, and alphabetically among words that appear the same number of times. Print every word whose counter of appearances equals that of the word at position $N$ , even when this makes the list longer than $N$ words. If the last 7 days hold fewer than $N$ words of interest, print all of them.

Constraints

Every word is made of lowercase letters only and is at most 20 characters long.
At most 20000 different words appear.
At most 20000 words appear per day.
Words shorter than four characters are of no interest and are never counted.
There are at most 1000 days.
$1 \le N \le 20$

Examples1

Example 1

Input

<text>
imagine you are in the hiring process of a company whose
main business is analyzing the information that appears
in the web
</text>

<text>
a simple test consists in writing a program for
maintaining up to date a set of trending topics
</text>

<text>
you will be hired depending on the efficiency of your solution
</text>

<top 5 />

<text>
they provide you with a file containing the text
corresponding to a highly active blog
</text>

<text>
the text is organized daily and you have to provide the
sorted list of the n most frequent words during last week
when asked
</text>


<text>
each input file contains one test case the text corresponding
to a day is delimited by tag text
</text>

<text>
the query of top n words can appear between texts corresponding
to two different days
</text>

<top 3 />

<text>
blah blah blah blah blah blah blah blah blah
please please please
</text>

<top 3 />

Expected output

<top 5>
analyzing 1
appears 1
business 1
company 1
consists 1
date 1
depending 1
efficiency 1
hired 1
hiring 1
imagine 1
information 1
main 1
maintaining 1
process 1
program 1
simple 1
solution 1
test 1
that 1
topics 1
trending 1
whose 1
will 1
writing 1
your 1
</top>
<top 3>
text 4
corresponding 3
file 2
provide 2
test 2
words 2
</top>
<top 3>
blah 9
text 4
corresponding 3
please 3
</top>