| Codeforces Round 416 (Div. 2) |
|---|
| Закончено |
В свободное время Владик оценивает красоту флагов.
Флаг можно представить как матрицу n × m из целых положительных чисел.
Определим красоту матрицы, как количество пятен в ней. Пятном назовем некоторое множество клеток с одинаковыми числами таких, что между любой парой клеток множества существует путь по смежным по стороне клеткам. Пример разделения матрицы на пятна:
Но в этот раз он решил что-то поменять и начать оценивать не весь флаг целиком, а только некоторый его отрезок. Отрезок флага можно описать как подматрицу матрицы флага с противоложными углами в (1, l) и (n, r), где 1 ≤ l ≤ r ≤ m.
Помогите Владику посчитать красоту для некоторых отрезков флага!
В первой строке заданы три целых числа n, m, q (1 ≤ n ≤ 10, 1 ≤ m, q ≤ 105) — размеры флага и количество отрезков соответственно.
В каждой из следующих n строк записано по m целых чисел — описание флага. Все элементы матрицы являются целыми натуральными числами не превышающими 106.
Следующие q строк будут содержать по два целых числа l, r (1 ≤ l ≤ r ≤ m) — границы отрезка для которого Владик хочет посчитать красоту.
Для каждого отрезка в отдельной строке выведите количество пятен на нем.
4 5 4
1 1 1 1 1
1 2 2 3 3
1 1 1 2 5
4 4 5 5 5
1 5
2 5
1 2
4 5
6
7
3
4
Разделение на пятна для каждого отрезка:
