Alice sở hữu $k$ kỷ niệm quý giá, mỗi kỷ niệm được gán một giá trị hạnh phúc duy nhất từ $1$ đến $k$ tương ứng với thứ tự thời gian chúng xảy ra. Để khám phá quá khứ của mình, cô ấy đã ghi lại một dãy gồm $n$ phép thuật. Phép thuật thứ $i$ sắp xếp lại các kỷ niệm của cô theo một hoán vị $A_i$. Khi một dãy liên tiếp các phép thuật được thực hiện, hiệu ứng của chúng kết hợp lại, tạo ra một sự sắp xếp phức tạp mới trong tâm trí cô.

Khi các phép thuật xáo trộn dòng thời gian của các kỷ niệm, một kỷ niệm xảy ra sau (có giá trị hạnh phúc cao hơn) có thể bị đặt trước một kỷ niệm xảy ra trước. Sự bất hòa về thời gian này tạo ra thứ mà Alice gọi là một cặp đáng tiếc — một khoảnh khắc mà thứ tự thời gian tự nhiên của hạnh phúc đã bị đảo ngược. Bị thúc đẩy bởi sự tò mò, cô ấy muốn đo lường tổng sự bất hòa cảm xúc bằng cách đếm mọi cặp đáng tiếc được tạo ra trên tất cả các đoạn liên tiếp có thể có của các phép thuật.

Một cách hình thức, bạn được cho $k$ kỷ niệm và một dãy $n$ hoán vị, trong đó hoán vị thứ $i$ được ký hiệu là $A_i$. Mỗi $A_i$ là một hoán vị của $\{1, 2, \ldots, k\}$. Với hai hoán vị $p$ và $q$, phép hợp thành $p \circ q$ được định nghĩa là $$(p\circ q)(x)=p(q(x)).$$

Với mọi đoạn liên tiếp các phép thuật $[l, r]$ (với $1 \le l \le r \le n$), gọi $P_{l,r}$ là hoán vị cuối cùng sau khi các phép thuật được kết hợp. Nó được định nghĩa là: (Do tính kết hợp của phép hợp thành hoán vị, cách đặt dấu ngoặc của tích này không quan trọng. Ví dụ, $(A_l\circ A_{l+1})\circ A_{l+2}=A_l\circ(A_{l+1}\circ A_{l+2})$. Thứ tự của các hoán vị được cố định như đã viết.)

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

Nhiệm vụ của bạn là tính tổng số lượng cặp đáng tiếc trên tất cả các đoạn liên tiếp của các phép thuật. Một cách hình thức, hãy tính: $$\sum_{1\le l\le r\le n}\operatorname{inv}(P_{l,r}),$$ trong đó $\operatorname{inv}(p)$ là số nghịch thế của hoán vị $p$, được định nghĩa chính thức là số cặp $(x,y)$ thỏa mãn $1\leq xp(y)$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $k$ ($1\le n,k\le 10^5$, $nk\le 10^5$).

Mỗi dòng trong số $n$ dòng tiếp theo chứa $k$ số nguyên. Dòng thứ $i$ trong số các dòng này chứa hoán vị $A_i(1),A_i(2),\ldots,A_i(k)$.

Dữ liệu ra

In ra một số nguyên trên một dòng, biểu thị kết quả.

Ví dụ

Dữ liệu vào 1

2 3
1 3 2
2 3 1

Dữ liệu ra 1

6

Dữ liệu vào 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

Dữ liệu ra 2

116

Ghi chú

Với test đầu tiên,

• Số nghịch thế của $A_1=[1,3,2]$ và $A_2=[2,3,1]$ lần lượt là $1$ và $2$.
• Phép hợp thành của chúng là $A_1\circ A_2=[3,2,1]$, có số nghịch thế là $3$.
• Tổng trên ba đoạn liên tiếp không rỗng là $1+2+3=6$.

Với test thứ hai, có $21$ đoạn liên tiếp. Phân theo độ dài đoạn, tổng số nghịch thế là [ 32,\ 28,\ 24,\ 12,\ 12,\ 8. ] Tổng của chúng là $116$.