Valera and Tubes

**题目描述** 有一个n×m的矩形网格 定义“管道”如下： 是一些格子组成的序列 序列长度至少为2 序列中任意相邻两个格子必须在网格中也相邻（四联通） 序列中不能出现重复的格子 现在要给出k个管道使得每个格子恰好属于一个管道 **输入格式** 一行 依次输入 n m 和 k（2≤n m≤300 2≤2k≤n×m） **输出格式** 每个管道所对应的序列 k行 由若干Xi和Yi组成 如果有多解 仅输出一种即可

Valera has got a rectangle table consisting of $ n $ rows and $ m $ columns. Valera numbered the table rows starting from one, from top to bottom and the columns – starting from one, from left to right. We will represent cell that is on the intersection of row $ x $ and column $ y $ by a pair of integers $ (x,y) $ . Valera wants to place exactly $ k $ tubes on his rectangle table. A tube is such sequence of table cells $ (x_{1},y_{1}) $ , $ (x_{2},y_{2}) $ , $ ... $ , $ (x_{r},y_{r}) $ , that: - $ r>=2 $ ; - for any integer $ i $ $ (1<=i<=r-1) $ the following equation $ |x_{i}-x_{i+1}|+|y_{i}-y_{i+1}|=1 $ holds; - each table cell, which belongs to the tube, must occur exactly once in the sequence. Valera thinks that the tubes are arranged in a fancy manner if the following conditions are fulfilled: - no pair of tubes has common cells; - each cell of the table belongs to some tube. Help Valera to arrange $ k $ tubes on his rectangle table in a fancy manner.

The first line contains three space-separated integers $ n,m,k $ ( $ 2<=n,m<=300 $ ; $ 2<=2k<=n·m $ ) — the number of rows, the number of columns and the number of tubes, correspondingly.

Print $ k $ lines. In the $ i $ -th line print the description of the $ i $ -th tube: first print integer $ r_{i} $ (the number of tube cells), then print $ 2r_{i} $ integers $ x_{i1},y_{i1},x_{i2},y_{i2},...,x_{iri},y_{iri} $ (the sequence of table cells). If there are multiple solutions, you can print any of them. It is guaranteed that at least one solution exists.

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

Picture for the first sample: Picture for the second sample: