Alice posee $k$ recuerdos preciosos, cada uno con un valor de felicidad único del $1$ al $k$, correspondiente al orden cronológico en que ocurrieron. Para explorar su pasado, ha inscrito una secuencia de $n$ hechizos mágicos. El $i$-ésimo hechizo reorganiza sus recuerdos según una permutación $A_i$. Cuando se lanza una secuencia continua de hechizos, sus efectos se combinan, creando una nueva y compleja reorganización de su mente.

A medida que los hechizos mezclan la línea temporal de sus recuerdos, un recuerdo posterior (con un valor de felicidad mayor) podría terminar colocado antes de un recuerdo anterior. Esta disonancia temporal crea lo que Alice llama un par de pesar: un momento en que el orden cronológico natural de la felicidad se ha invertido. Impulsada por la curiosidad, desea medir la disonancia emocional total contando cada par de pesar generado a lo largo de todos los segmentos contiguos posibles de hechizos.

Formalmente, se te dan $k$ recuerdos y una secuencia de $n$ permutaciones, donde la $i$-ésima permutación se denota como $A_i$. Cada $A_i$ es una permutación de $\{1, 2, \ldots, k\}$. Para dos permutaciones cualesquiera $p$ y $q$, su composición $p \circ q$ se define como $$(p\circ q)(x)=p(q(x)).$$

Para cualquier segmento contiguo de hechizos $[l, r]$ (donde $1 \le l \le r \le n$), sea $P_{l,r}$ la permutación final después de combinar los hechizos. Se define como: (Por la asociatividad de la composición de permutaciones, el parentizado de este producto no importa. Por ejemplo, $(A_l\circ A_{l+1})\circ A_{l+2}=A_l\circ(A_{l+1}\circ A_{l+2})$. El orden de las permutaciones está fijo como está escrito.)

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

Tu tarea es calcular el número total de pares de pesar a lo largo de todos los segmentos contiguos de hechizos. Formalmente, calcula: $$\sum_{1\le l\le r\le n}\operatorname{inv}(P_{l,r}),$$ donde $\operatorname{inv}(p)$ denota el número de inversiones en la permutación $p$, definido formalmente como el número de pares $(x,y)$ tales que $1\leq xp(y)$.

Entrada

La primera línea contiene dos enteros $n$ y $k$ ($1\le n,k\le 10^5$, $nk\le 10^5$).

Cada una de las siguientes $n$ líneas contiene $k$ enteros. La $i$-ésima de estas líneas contiene la permutación $A_i(1),A_i(2),\ldots,A_i(k)$.

Salida

Imprime un solo entero en una línea, que denota la respuesta.

Ejemplos

Entrada 1

2 3
1 3 2
2 3 1

Salida 1

6

Entrada 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

Salida 2

116

Nota

Para el primer caso,

• Los conteos de inversiones de $A_1=[1,3,2]$ y $A_2=[2,3,1]$ son $1$ y $2$.
• Su composición es $A_1\circ A_2=[3,2,1]$, cuyo conteo de inversiones es $3$.
• Sumando los tres segmentos contiguos no vacíos se obtiene $1+2+3=6$.

Para el segundo caso, hay $21$ segmentos contiguos. Agrupados por longitud de segmento, las sumas de los conteos de inversiones son [ 32,\ 28,\ 24,\ 12,\ 12,\ 8. ] Su total es $116$.