#860 Formation

Statement

Statement language

If recruits learn these maneuvers through constant practice, they will be able to carry them out more easily in battle itself.

Vegetius, Epitome of Military Science, Book I, Chapter 26

The army you command must change formations as the battle unfolds. However, if changing formations requires many commands, the army may struggle to respond to a sudden change in battle. You want to identify weaknesses in formation changes and improve the training.

The units are numbered $1$ through $K$ . Each formation places the $K$ units in a line and is represented by their numbers in order from the left flank to the right flank. One command can swap the positions of two neighboring units.

You are given the $N$ formations you have prepared. For each formation, find the maximum, over the other $N$ formations, of the minimum number of commands needed to change to that formation. Intermediate formations do not have to appear in the given list.

Input

The first line contains integers $K$ and $N$ , separated by a space.

Each of the next $N$ lines contains unit numbers $p_{i,1},p_{i,2},\ldots,p_{i,K}$ for a formation in order from the left flank to the right flank, separated by spaces.

Output

Print the answer for each formation on its own line, in the given order.

Constraints

$2\le K\le9$
$2\le N\le200\,000$
$1\le p_{i,j}\le K$

Samples

Sample 1

Input

Output

5
4
5

In the first example, changing between the first and second formations requires at least $4$ commands. Changing between the first and third requires at least $5$ commands, and changing between the second and third requires at least $3$ commands.

Sample 2

Input

2
1 3
3 1

Output

1
1

In the second example, swapping the middle unit and the unit at the right end once changes one formation into the other.