| Codeforces Round 252 (Div. 2) |
|---|
| Закончено |
У Валеры есть прямоугольная таблица, состоящая из n строк и m столбцов. Валера пронумеровал строки таблицы, начиная от единицы, сверху вниз, а столбцы — начиная от единицы, слева направо. Ячейку, расположенную на пересечении строки x и столбца y, будем обозначать парой чисел (x, y).
Валера хочет разместить ровно k труб на своей прямоугольной таблице. Трубой будем называть такую последовательность ячеек таблицы (x1, y1), (x2, y2), ..., (xr, yr), что:
- r ≥ 2;
- для любого целого i (1 ≤ i ≤ r - 1) выполняется равенство |xi - xi + 1| + |yi - yi + 1| = 1;
- каждая ячейка, принадлежащая трубе, встречается в последовательности ячеек ровно один раз.
Валера считает, что трубы размещены красиво, если выполнены условия:
- никакая пара труб не имеет общих ячеек;
- каждая ячейка таблицы принадлежит некоторой трубе.
Помогите Валере красиво разместить k труб на его прямоугольной таблице.
В первой строке задано три целых числа через пробел n, m, k (2 ≤ n, m ≤ 300; 2 ≤ 2k ≤ n·m) — количество строк, количество столбцов и количество труб, соответственно.
Выведите k строк. В i-й строке выведите описание i-й трубы: сначала выведите целое число ri (количество ячеек трубы), затем выведите 2ri целых чисел xi1, yi1, xi2, yi2, ..., xiri, yiri (последовательность ячеек таблицы).
Если существует несколько решений, разрешается вывести любое. Гарантируется, что хотя бы одно решение существует.
3 3 3
3 1 1 1 2 1 3
3 2 1 2 2 2 3
3 3 1 3 2 3 3
2 3 1
6 1 1 1 2 1 3 2 3 2 2 2 1
Иллюстрация к первому примеру:
Иллюстрация ко второму примеру:
