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

**days.**

`K`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

**, separated by a space.**

`K`Each of the following

**lines contains the following:**

`N`- The name of a subreddit.
space-separated integers, denoting the number of subscribers for each day.`K`

### Output

The output should contain ** K** lines. The

**line should contain the name of day**

`i`^{th}**'s**

`i`*Subreddit of the Day*, or

**if there isn't one.**

`none`### Constraints

`3 ≤ N, K ≤ 100``1 ≤ any number of subscribers ≤ 10`^{6}`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 | nonenone /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
and`i ∈ S`denotes the fact that subreddit`j ∈ D`can be declared`i`*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.