Alice possesses $k$ precious memories, each assigned a unique happiness value from $1$ to $k$ corresponding to the chronological order in which they occurred. To explore her past, she has inscribed a sequence of $n$ magical spells. The $i$-th spell rearranges her memories according to a permutation $A_i$. When a continuous sequence of spells is cast, their effects compound, creating a new, complex rearrangement of her mind.

As spells shuffle the timeline of her memories, a later memory (one with a higher happiness value) might end up placed before an earlier memory. This temporal dissonance creates what Alice calls a regretful pair---a moment where the natural chronological order of happiness has been inverted. Driven by curiosity, she wishes to measure the total emotional dissonance by counting every regretful pair generated across all possible contiguous segments of spells.

Formally, you are given $k$ memories and a sequence of $n$ permutations, where the $i$-th permutation is denoted as $A_i$. Each $A_i$ is a permutation of $\{1, 2, \ldots, k\}$. For any two permutations $p$ and $q$, their composition $p \circ q$ is defined as $$(p\circ q)(x)=p(q(x)).$$

For any contiguous segment of spells $[l, r]$ (where $1 \le l \le r \le n$), let $P_{l,r}$ represent the final permutation after the spells are compounded. It is defined as: (By associativity of permutation composition, the parenthesization of this product does not matter. For example, $(A_l\circ A_{l+1})\circ A_{l+2}=A_l\circ(A_{l+1}\circ A_{l+2})$. The order of the permutations is fixed as written.)

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

Your task is to compute the total number of regretful pairs across all contiguous segments of spells. Formally, calculate: $$\sum_{1\le l\le r\le n}\operatorname{inv}(P_{l,r}),$$ where $\operatorname{inv}(p)$ denotes the number of inversions in permutation $p$, formally defined as the number of pairs $(x,y)$ such that $1\leq xp(y)$.

Input

The first line contains two integers $n$ and $k$ ($1\le n,k\le 10^5$, $nk\le 10^5$).

Each of the next $n$ lines contains $k$ integers. The $i$-th of these lines contains the permutation $A_i(1),A_i(2),\ldots,A_i(k)$.

Output

Print one integer on a line, denoting the answer.

Examples

Input 1

2 3
1 3 2
2 3 1

Output 1

6

Input 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

Output 2

116

Note

For the first test,

• The inversion counts of $A_1=[1,3,2]$ and $A_2=[2,3,1]$ are $1$ and $2$.
• Their composition is $A_1\circ A_2=[3,2,1]$, whose inversion count is $3$.
• Summing over the three non-empty contiguous segments gives $1+2+3=6$.

For the second test, there are $21$ contiguous segments. Grouped by segment length, the sums of inversion counts are [ 32,\ 28,\ 24,\ 12,\ 12,\ 8. ] Their total is $116$.