你最近学习了逆序数的 $O(n \log n)$ 算法。

给定长度为 $n$ 的排列 $P$，定义对 $P$ 的一次操作如下：

选择 $i$ 和 $j$ 满足 $1 \leq i < j \leq n$ 且 $P_i > P_j$，然后交换 $P_i$ 和 $P_j$。

对于排列 $A$ 和排列 $B$，如果排列 $A$ 经过一些操作变成了排列 $B$，则称 $B$ 是从 $A$ 可达的。

现在有 $m$ 个长度为 $n$ 的排列 $P_1, P_2, \cdots, P_m$，记 $f_i$ 为从 $P_j$ 可达 $P_i$ 的 $j$ 的个数，试求所有 $f_i$ 的值。

输入格式

第一行包含两个正整数，$n$ 和 $m$，分别表示排列长度和排列的个数。

接下来 $m$ 行，每行 $n$ 个数描述一个排列。

输出格式

共 $m$ 行，其中第 $i$ 行输出 $f_i$。

样例一

input

3 3
1 2 3
3 1 2
2 3 1

output

3
1
1

样例二

input

2 2
1 2
1 2

output

2
2

数据范围与提示

• 子任务 $1$（$10$ 分）：$n \leq 7, m \leq 2000$。
• 子任务 $2$（$22$ 分）：$n \leq 8$。
• 子任务 $3$（$19$ 分）：$m \leq 2000$。
• 子任务 $4$（$49$ 分）：无特殊限制。

对于 $100\%$ 的数据，$1 \leq n \leq 9$，$1 \leq m \leq 3 \times 10^5$。

时间限制：$\texttt{3s}$

空间限制：$\texttt{512MB}$