You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

你需要解决一个高维偏序问题。

Description

一个二维数组$A[K][N]$的偏序问题，指的就是求所有满足如下条件的数对$(i,j)$的个数：

• $i<j$
• $A[p][i]<A[p][j]$，其中$p\in\{0,1,\dots,K-1\}$

其中，保证任意$A[p][1]$~$A[p][N]$是一个$1$~$N$的排列。

Format

Input

第一行SubTask编号∈{0,1,2,3}（意义见Limitation）；

第二行两个数字N,K，意义同题目描述；

接下来K行，每行N个数字，表示了这个二维数组。

Output

一行一个整数，表示题目描述所求偏序的答案。

（提示：答案不超过$\frac{N*(N-1)}{2}$）

Samples

3
5 3
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

10

Limitation

空间限制：256MB

对于每个25分的SubTask，你需要处理不同的数据：

SubTask 0：N=3000000，K=1，1500毫秒

SubTask 1：N=500000，K=2，1500毫秒

SubTask 2：N=20000，K=100，5000毫秒

SubTask 3：N=60000，K=12，5000毫秒