Reddit, the front page of the internet, is made up of N different subreddits. The popularity (defined as the number of subscribers) of these communities is tracked daily, for a period of K days.
Each day, one community can be declared Subreddit of the Day, if it meets the following criteria:
- During the past 3 days, its number of subscribers has been strictly growing.
- It has not been declared Subreddit of the Day in the past.
Note that it is possible to have days with no Subreddit of the Day. If there are multiple eligible communities, you can choose any of them. Your task is to maximize the number of days which have a Subreddit of the Day.
Input
The first line of input contains integers N and K, separated by a space.
Each of the following N lines contains the following:
- The name of a subreddit.
- K space-separated integers, denoting the number of subscribers for each day.
Output
The output should contain K lines. The ith line should contain the name of day i's Subreddit of the Day, or none if there isn't one.
Constraints
- 3 ≤ N, K ≤ 100
- 1 ≤ any number of subscribers ≤ 106
- Subreddit names contain at most 25 characters: lowercase and uppercase English letters, digits, underscores and forward slashes.
Sample
| Input | Output | Explanation |
|---|---|---|
| 3 5 /r/AskReddit 10000 15000 15023 15009 18000 /r/Romania 800 750 920 990 999 /r/aww 99995 99996 99997 99998 99999 | none none /r/AskReddit /r/Romania /r/aww | /r/AskReddit is only eligible for day 3. /r/Romania is eligible for days 4 and 5. /r/aww is eligible for days 3, 4 and 5. |
Given a subreddit, determining all days in which it can be declared Subreddit of the Day is a trivial task.
Now, consider the following:
- S = the set of all N subreddits
- D = the set of all K days
- an edge between i ∈ S and j ∈ D denotes the fact that subreddit i can be declared Subreddit of the Day on day j.
Using this model, the problem becomes equivalent to finding a maximum matching in a bipartite graph.
Further reading: infoarena.
