你最近学习了逆序数的 $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}$