D. Инна и матрица конфет
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Инна очень любит сладкое. Поэтому она решила сыграть в игру «Матрица конфет».

Перед Инной матрица размером n × m и k конфет. Будем нумеровать строки матрицы от 1 до n, а столбцы — от 1 до m. Ячейку в i-ой строке и j-ом столбце будем обозначать (i, j). Две ячейки (i, j) и (p, q) матрицы будем называть смежными, если |i - p| + |j - q| = 1. Маршрутом будем называть последовательность ячеек матрицы, в которой каждая пара соседних (в последовательности) ячеек смежна. Количество ячеек в последовательности будем называть длиной маршрута.

В каждой ячейке матрицы может лежать не более одной конфеты. Изначально все ячейки пустые. Инна пытается разместить каждую из k конфет в матрице по очереди. Для каждой конфеты Инна выбирает ячейку (i, j), в которой будет лежать конфета, а также выбирает маршрут, начинающийся в ячейке (1, 1), заканчивающийся в ячейке (i, j) и не содержащий конфет. После чего Инна проводит конфету по маршруту от клетки (1, 1) до клетки (i, j), где конфета остается навсегда. Если в какой-то момент Инна не может выбрать маршрут для конфеты, она проигрывает. Если же Инне удается разместить все конфеты в матрице описанным способом, то ее штраф равен сумме длин всех маршрутов, которые она использовала.

Помогите Инне минимизировать штраф в игре.

Входные данные

Единственная строка входных данных содержит три целых числа n, m и k (1 ≤ n, m ≤ 50, 1 ≤ k ≤ n·m).

Выходные данные

В первой строке выведите целое число — минимальный штраф Инны в игре.

В следующих k строках выведите описание маршрута для каждой конфеты. Описание маршрута i-ой в порядке размещения конфеты должно находится в i-ой строке. Описание маршрута — это последовательность ячеек. Каждая ячейка должна быть записана в формате (i, j), где i — номер строки ячейки, а j — номер столбца. Разрешается выводить в строке дополнительные пробельные символы. Если существует несколько оптимальных решений — выведите любое.

Строго следуйте формату вывода! Если ваша программа прошла первый претест, значит формат вывода правильный.

Примеры
Входные данные
4 4 4
Выходные данные
8
(1,1) (2,1) (2,2)
(1,1) (1,2)
(1,1) (2,1)
(1,1)
Примечание

Пояснение к примеру. Изначально матрица пуста. Далее Инна прокладывает первый маршрут, штраф за него равен количеству ячеек в нем — 3. Заметим, что теперь ни один маршрут не может пройти через ячейку (2, 2), так как в ней теперь лежит конфета. Следующие две конфеты попадают в ячейки (1, 2) и (2, 1). Последнюю конфету Инна просто оставляет в ячейке (1, 1), маршрут содержит только ее. Суммарный штраф равен: 3 + 2 + 2 + 1 = 8.

Заметим, что Инна не могла оставить в ячейке (1, 1), к примеру, третью конфету, в этом случае она не смогла бы проложить маршрут для четвертой конфеты.