앨리스는 $k$개의 소중한 추억을 가지고 있으며, 각 추억에는 발생한 시간 순서대로 $1$부터 $k$까지의 고유한 행복도 값이 할당되어 있다. 그녀는 과거를 탐구하기 위해 $n$개의 마법 주문을 차례대로 새겨 놓았다. $i$번째 주문은 순열 $A_i$에 따라 그녀의 추억들을 재배열한다. 연속된 주문들이 시전되면 그 효과들이 합성되어, 새로운 복잡한 재배열이 만들어진다.

주문들이 추억들의 시간 순서를 뒤섞으면서, 더 나중의 추억(더 높은 행복도를 가진)이 더 이른 추억보다 앞에 위치할 수 있다. 이러한 시간적 불일치는 앨리스가 후회스러운 쌍(regretful pair)이라고 부르는, 행복도의 자연스러운 시간 순서가 뒤집힌 순간을 만들어낸다. 호기심에 이끌린 그녀는 가능한 모든 연속적인 주문 구간에 대해 생성된 모든 후회스러운 쌍을 세어 전체적인 감정적 불일치를 측정하고자 한다.

형식적으로, $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$의 역전(inversion) 개수, 즉 $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$이다.