愛麗絲擁有 $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}$ 表示咒語疊加後的最終排列。其定義為：（根據排列複合的結合律，這個乘積的括號化方式無關緊要。例如，$(A_l\circ A_{l+1})\circ A_{l+2}=A_l\circ(A_{l+1}\circ A_{l+2})$。排列的順序按書寫固定。）

$$P_{l,r}=A_l\circ A_{l+1}\circ\cdots\circ A_r.$$

你的任務是計算所有連續咒語區間中遺憾對的總數。正式地，計算： $$\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$。