Alice possède $k$ souvenirs précieux, chacun se voit attribuer une valeur de bonheur unique de $1$ à $k$ correspondant à l'ordre chronologique de leur occurrence. Pour explorer son passé, elle a inscrit une séquence de $n$ sorts magiques. Le $i$-ème sort réorganise ses souvenirs selon une permutation $A_i$. Lorsqu'une séquence continue de sorts est lancée, leurs effets se combinent, créant un nouvel arrangement complexe de son esprit.

Alors que les sorts mélangent la chronologie de ses souvenirs, un souvenir plus tardif (avec une valeur de bonheur plus élevée) pourrait se retrouver placé avant un souvenir plus ancien. Cette dissonance temporelle crée ce qu'Alice appelle une paire regrettable — un moment où l'ordre chronologique naturel du bonheur a été inversé. Poussée par la curiosité, elle souhaite mesurer la dissonance émotionnelle totale en comptant chaque paire regrettable générée sur tous les segments contigus possibles de sorts.

Formellement, on vous donne $k$ souvenirs et une séquence de $n$ permutations, où la $i$-ème permutation est notée $A_i$. Chaque $A_i$ est une permutation de $\{1, 2, \ldots, k\}$. Pour deux permutations quelconques $p$ et $q$, leur composition $p \circ q$ est définie par $$(p\circ q)(x)=p(q(x)).$$

Pour tout segment contigu de sorts $[l, r]$ (où $1 \le l \le r \le n$), soit $P_{l,r}$ la permutation finale après combinaison des sorts. Elle est définie par : (Par associativité de la composition des permutations, le parenthésage de ce produit n'a pas d'importance. Par exemple, $(A_l\circ A_{l+1})\circ A_{l+2}=A_l\circ(A_{l+1}\circ A_{l+2})$. L'ordre des permutations est fixé comme écrit.)

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

Votre tâche est de calculer le nombre total de paires regrettables sur tous les segments contigus de sorts. Formellement, calculez : $$\sum_{1\le l\le r\le n}\operatorname{inv}(P_{l,r}),$$ où $\operatorname{inv}(p)$ désigne le nombre d'inversions dans la permutation $p$, formellement défini comme le nombre de paires $(x,y)$ telles que $1\leq xp(y)$.

Entrée

La première ligne contient deux entiers $n$ et $k$ ($1\le n,k\le 10^5$, $nk\le 10^5$).

Chacune des $n$ lignes suivantes contient $k$ entiers. La $i$-ème de ces lignes contient la permutation $A_i(1),A_i(2),\ldots,A_i(k)$.

Sortie

Afficher un entier sur une ligne, désignant la réponse.

Exemples

Entrée 1

2 3
1 3 2
2 3 1

Sortie 1

6

Entrée 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

Sortie 2

116

Remarque

Pour le premier test,

• Les nombres d'inversions de $A_1=[1,3,2]$ et $A_2=[2,3,1]$ sont $1$ et $2$.
• Leur composition est $A_1\circ A_2=[3,2,1]$, dont le nombre d'inversions est $3$.
• La somme sur les trois segments contigus non vides donne $1+2+3=6$.

Pour le deuxième test, il y a $21$ segments contigus. Groupés par longueur de segment, les sommes des nombres d'inversions sont [ 32,\ 28,\ 24,\ 12,\ 12,\ 8. ] Leur total est $116$.