Subreddits

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

InputOutputExplanation
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.
Questions?

Sponsors Gold