你最近学习了逆序数的 O(nlogn) 算法。
给定长度为 n 的排列 P,定义对 P 的一次操作如下:
选择 i 和 j 满足 1≤i<j≤n 且 Pi>Pj,然后交换 Pi 和 Pj。
对于排列 A 和排列 B,如果排列 A 经过一些操作变成了排列 B,则称 B 是从 A 可达的。
现在有 m 个长度为 n 的排列 P1,P2,⋯,Pm,记 fi 为从 Pj 可达 Pi 的 j 的个数,试求所有 fi 的值。
输入格式
第一行包含两个正整数,n 和 m,分别表示排列长度和排列的个数。
接下来 m 行,每行 n 个数描述一个排列。
输出格式
共 m 行,其中第 i 行输出 fi。
样例一
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≤7,m≤2000。
- 子任务 2(22 分):n≤8。
- 子任务 3(19 分):m≤2000。
- 子任务 4(49 分):无特殊限制。
对于 100% 的数据,1≤n≤9,1≤m≤3×105。
时间限制:3s
空间限制:512MB