У Егора есть табличка \(n \times m\), где строки пронумерованы от \(1\) до \(n\) сверху вниз, а столбцы пронумерованы с \(1\) до \(m\) слева направо. Каждая клетка таблички покрашена в некоторый цвет, где цвета пронумерованы целыми числами от \(1\) до \(10^5\).
Будем обозначать клетку, которая находится на пересечении \(r\)-й строки и \(c\)-го столбца, как \((r, c)\). Определим манхэттенское расстояние между клетками \((r_1, c_1)\) и \((r_2, c_2)\) как длину кратчайшего пути между этими клетками, в котором любые две соседние клетки имеют общую сторону. Например, в таблице \(3 \times 4\) манхэттенское расстояние между клетками \((1, 2)\) и \((3, 3)\) равно \(3\), и один из кратчайших путей имеет вид \((1, 2) \to (2, 2) \to (2, 3) \to (3, 3)\). Обратите внимание, что путь может проходить по клеткам любого цвета.
У Егора возникло желание посчитать сумму манхэттенских расстояний по всем парам клеток одного цвета. Помогите Егору — вычислите эту сумму.
Примечание
В первом примере есть три пары клеток с одинаковым цветом: в координатах \((1, 1)\) и \((2, 3)\), в координатах \((1, 2)\) и \((2, 2)\), в координатах \((1, 3)\) и \((2, 1)\). Соответствующие манхеттенские расстояния равны \(3\), \(1\) и \(3\), их сумма равна \(7\).