У Алисы есть $k$ драгоценных воспоминаний, каждому из которых присвоено уникальное значение счастья от $1$ до $k$, соответствующее хронологическому порядку их возникновения. Чтобы исследовать своё прошлое, она записала последовательность из $n$ магических заклинаний. $i$-е заклинание переставляет её воспоминания в соответствии с перестановкой $A_i$. Когда произносится непрерывная последовательность заклинаний, их эффекты объединяются, создавая новое, сложное переупорядочивание её разума.

По мере того как заклинания перемешивают временную линию её воспоминаний, более позднее воспоминание (с большим значением счастья) может оказаться перед более ранним. Эта временная диссонирующая ситуация создаёт то, что Алиса называет парой сожаления — момент, когда естественный хронологический порядок счастья был нарушен. Движимая любопытством, она хочет измерить общий эмоциональный диссонанс, подсчитав каждую пару сожаления, возникающую во всех возможных непрерывных сегментах заклинаний.

Формально, даны $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$, формально определяемое как число пар $(x,y)$ таких, что $1\leq xp(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$.