【模板】k维偏序

题目描述

给你 $k$ 个长为 $n$ 的数列 $A[1..k][1..n]$,$f(i)=\sum\limits_{j=1}^n[\forall 1\le d\le k,\,A[d][j]<A[d][i]]$,求出所有 $f(1..n)$。

输入输出格式

输入格式


第一行两个正整数 $n,\,k$。 后面 $n$ 行每行 $k$ 个正整数,表示 $A[1..k][i]$。

输出格式


$n$ 行,每行一个正整数分别表示 $f(1..n)$。

输入输出样例

输入样例 #1

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

输出样例 #1

3
3
0
0
0
0
0
0
0
0

输入样例 #2

4 2
5 3
2 7
1 4
3 9

输出样例 #2

0
1
0
2

说明

~~这题的数据范围应该是n=1e10,时限开1e11s,卡掉n^2k做法~~ $1\le n\le 1000$,$2\le k\le 8$,$1\le A[i][j]\le 10^9$。 这题暴力跑的会比某些复杂度优秀的做法快,然而用暴力水过去挺没意思的..