You have recently learned the $O(n \log n)$ algorithm for counting inversions.

Given a permutation $P$ of length $n$, an operation on $P$ is defined as follows:

Choose $i$ and $j$ such that $1 \leq i < j \leq n$ and $P_i > P_j$, then swap $P_i$ and $P_j$.

For two permutations $A$ and $B$, $B$ is said to be reachable from $A$ if $A$ can be transformed into $B$ through a sequence of operations.

There are $m$ permutations of length $n$, denoted as $P_1, P_2, \cdots, P_m$. Let $f_i$ be the number of indices $j$ such that $P_i$ is reachable from $P_j$. Calculate the values of all $f_i$.

Input

The first line contains two positive integers, $n$ and $m$, representing the length of the permutations and the number of permutations, respectively.

The next $m$ lines each contain $n$ integers describing a permutation.

Output

Output $m$ lines, where the $i$-th line contains the value of $f_i$.

Examples

Input 1

3 3
1 2 3
3 1 2
2 3 1

Output 1

3
1
1

Input 2

2 2
1 2
1 2

Output 2

2
2

Subtasks

• Subtask 1 (10 points): $n \leq 7, m \leq 2000$.
• Subtask 2 (22 points): $n \leq 8$.
• Subtask 3 (19 points): $m \leq 2000$.
• Subtask 4 (49 points): No additional constraints.

For $100\%$ of the data, $1 \leq n \leq 9$ and $1 \leq m \leq 3 \times 10^5$.