В свободное время Владик оценивает красоту флагов.
Флаг можно представить как матрицу n × m из целых положительных чисел.
Определим красоту матрицы, как количество пятен в ней. Пятном назовем некоторое множество клеток с одинаковыми числами таких, что между любой парой клеток множества существует путь по смежным по стороне клеткам. Пример разделения матрицы на пятна:
Но в этот раз он решил что-то поменять и начать оценивать не весь флаг целиком, а только некоторый его отрезок. Отрезок флага можно описать как подматрицу матрицы флага с противоложными углами в (1, l) и (n, r), где 1 ≤ l ≤ r ≤ m.
Помогите Владику посчитать красоту для некоторых отрезков флага!