Alice 拥有 $k$ 段珍贵的记忆，每段记忆被赋予一个从 $1$ 到 $k$ 的独特幸福值，对应其发生的先后顺序。为了探索她的过去，她刻下了一串由 $n$ 个魔法咒语组成的序列。第 $i$ 个咒语按照一个排列 $A_i$ 重新排列她的记忆。当连续的一段咒语被施放时，它们的效果会复合，形成一种新的、复杂的记忆排列。

当咒语打乱了记忆的时间线时，一段更晚的记忆（具有更高幸福值）可能会被放到一段更早的记忆之前。这种时间上的不和谐产生了一种逆序对——即幸福值的自然时间顺序被颠倒的时刻。出于好奇，她想要度量在所有可能的连续咒语段中产生的所有逆序对的总数，即总情感不和谐程度。

形式化地，给定 $k$ 段记忆和一个由 $n$ 个排列组成的序列，其中第 $i$ 个排列记为 $A_i$。每个 $A_i$ 是 $\{1, 2, \ldots, k\}$ 的一个排列。对于两个排列 $p$ 和 $q$，它们的复合 $p \circ q$ 定义为 $$(p\circ q)(x)=p(q(x)).$$

对于任意连续的咒语段 $[l, r]$（其中 $1 \le l \le r \le n$），令 $P_{l,r}$ 表示咒语复合后的最终排列。其定义为： $$P_{l,r}=A_l\circ A_{l+1}\circ\cdots\circ A_r.$$ （由排列复合的结合性，该乘积的括号化方式不影响结果。例如，$(A_l\circ A_{l+1})\circ A_{l+2}=A_l\circ(A_{l+1}\circ A_{l+2})$。排列的顺序按书写固定。）

你的任务是计算所有连续咒语段中逆序对的总数。形式化地，计算： $$\sum_{1\le l\le r\le n}\operatorname{inv}(P_{l,r}),$$ 其中 $\operatorname{inv}(p)$ 表示排列 $p$ 中逆序对的数量，形式化定义为满足 $1\leq xp(y)$ 的 $(x,y)$ 对数。

输入格式

第一行包含两个整数 $n$ 和 $k$（$1\le n,k\le 10^5$，$nk\le 10^5$）。

接下来 $n$ 行，每行包含 $k$ 个整数。第 $i$ 行给出排列 $A_i(1),A_i(2),\ldots,A_i(k)$。

输出格式

输出一行一个整数，表示答案。

样例

样例输入 1

2 3
1 3 2
2 3 1

样例输出 1

6

样例输入 2

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

样例输出 2

116

说明

对于第一个测试：

• $A_1=[1,3,2]$ 和 $A_2=[2,3,1]$ 的逆序对数分别为 $1$ 和 $2$。
• 它们的复合是 $A_1\circ A_2=[3,2,1]$，逆序对数为 $3$。
• 对三个非空连续段求和得到 $1+2+3=6$。

对于第二个测试，共有 $21$ 个连续段。按段长分组，各组的逆序对数和为 [ 32,\ 28,\ 24,\ 12,\ 12,\ 8. ] 它们的总和是 $116$。