Alice posiada $k$ cennych wspomnień, każde z unikalną wartością szczęścia od $1$ do $k$, odpowiadającą chronologicznej kolejności ich występowania. Aby zbadać swoją przeszłość, zapisała sekwencję $n$ magicznych zaklęć. $i$-te zaklęcie przestawia jej wspomnienia zgodnie z permutacją $A_i$. Gdy rzucona zostanie ciągła sekwencja zaklęć, ich efekty łączą się, tworząc nowe, złożone przestawienie jej umysłu.

Ponieważ zaklęcia tasują oś czasu jej wspomnień, późniejsze wspomnienie (o wyższej wartości szczęścia) może znaleźć się przed wcześniejszym wspomnieniem. Ta czasowa dysonans tworzy to, co Alicja nazywa żałosną parą – moment, w którym naturalny porządek chronologiczny szczęścia został odwrócony. Kierowana ciekawością, chce zmierzyć całkowitą emocjonalną dysonans, zliczając każdą żałosną parę wygenerowaną we wszystkich możliwych spójnych segmentach zaklęć.

Formalnie, dane są $k$ wspomnień oraz ciąg $n$ permutacji, gdzie $i$-ta permutacja jest oznaczona jako $A_i$. Każde $A_i$ jest permutacją zbioru $\{1, 2, \ldots, k\}$. Dla dowolnych dwóch permutacji $p$ i $q$, ich złożenie $p \circ q$ definiujemy jako $$(p\circ q)(x)=p(q(x)).$$

Dla dowolnego spójnego segmentu zaklęć $[l, r]$ (gdzie $1 \le l \le r \le n$), niech $P_{l,r}$ oznacza końcową permutację po złożeniu zaklęć. Definiujemy ją jako: (Z powodu łączności składania permutacji, rozmieszczenie nawiasów w tym iloczynie nie ma znaczenia. Na przykład $(A_l\circ A_{l+1})\circ A_{l+2}=A_l\circ(A_{l+1}\circ A_{l+2})$. Kolejność permutacji jest ustalona tak, jak zapisano.)

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

Twoim zadaniem jest obliczenie całkowitej liczby żałosnych par we wszystkich spójnych segmentach zaklęć. Formalnie, oblicz: $$\sum_{1\le l\le r\le n}\operatorname{inv}(P_{l,r}),$$ gdzie $\operatorname{inv}(p)$ oznacza liczbę inwersji w permutacji $p$, formalnie zdefiniowaną jako liczba par $(x,y)$ takich, że $1\leq xp(y)$.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n$ i $k$ ($1\le n,k\le 10^5$, $nk\le 10^5$).

Każdy z kolejnych $n$ wierszy zawiera $k$ liczb całkowitych. $i$-ty z tych wierszy zawiera permutację $A_i(1),A_i(2),\ldots,A_i(k)$.

Wyjście

Wypisz jedną liczbę całkowitą w wierszu, oznaczającą odpowiedź.

Przykład

Wejście 1

2 3
1 3 2
2 3 1

Wyjście 1

6

Wejście 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

Wyjście 2

116

Uwagi

Dla pierwszego testu:

• Liczby inwersji $A_1=[1,3,2]$ i $A_2=[2,3,1]$ wynoszą odpowiednio $1$ i $2$.
• Ich złożenie to $A_1\circ A_2=[3,2,1]$, którego liczba inwersji wynosi $3$.
• Suma po trzech niepustych spójnych segmentach daje $1+2+3=6$.

Dla drugiego testu istnieje $21$ spójnych segmentów. Pogrupowane według długości segmentu, sumy liczb inwersji to [ 32,\ 28,\ 24,\ 12,\ 12,\ 8. ] Ich suma wynosi $116$.