Inna非常喜欢甜食。这就是为什么她决定玩一款名为“甜蜜矩阵”的游戏。
Inna 看到一个 n × m 矩阵和 k 颗糖果。我们将对矩阵行从 1 到 n 以及矩阵列从 1 到 m 进行索引。我们将第 i 行第 j 列中的单元格表示为 (i, j)。如果 |i - p|,则矩阵的两个单元 (i, j) 和 (p, q) 相邻+ |j - q| = 1。路径是矩阵单元的序列,其中序列中的每对相邻单元都是相邻的。我们将序列中的单元数称为路径长度。
矩阵的每个单元格最多可以有一颗糖果。最初,所有单元格都是空的。 Inna 试图将 k 颗糖果一一放入矩阵中。对于每个糖果,Inna 选择将包含糖果的单元格 (i, j),并选择从单元格 (1, 1) 开始并以单元格 (i, j) 结束且不包含任何糖果的路径。之后,Inna 将糖果沿着从单元格 (1, 1) 到单元格 (i, j) 的路径移动,糖果永远停留在单元格中。如果在某个时刻伊娜无法选择糖果的路径,她就输了。如果 Inna 可以按照所描述的方式将所有糖果放入矩阵中,那么她的惩罚等于她使用的所有路径的长度之和。
帮助Inna将比赛中的处罚降到最低。
输入
输入的第一行包含三个整数 n、m 和 k (1 ≤ n, m ≤ 50, 1 ≤ k ≤ n·m)。
输出
在第一行打印一个整数——Inna 在游戏中的最小罚分。
在接下来的 k 行中打印每个糖果的路径描述。第 i 行糖果的路径描述应位于第 i 行。路径的描述是单元序列。每个单元格必须以 (i, j) 格式编写,其中 i 是行号,j 是列号。您可以在行中打印额外的空格。如果有多个最优解,则打印其中任意一个。
请严格遵循输出格式!如果您的程序通过了第一次预测试,则输出格式是正确的。
示例
输入 #1
4 4 4
输出 #1
8 (1,1) (2,1) (2,2) (1,1) (1,2) (1,1) (2,1) (1,1)
注意
示例注释。最初矩阵是空的。然后 Inna 沿着她的第一条路径走,路径惩罚等于其中的单元格数量 - 3。请注意,现在没有路径可以通过单元格 (2, 2),因为它现在包含糖果。接下来的两颗糖果进入单元格 (1, 2) 和 (2, 1)。 Inna 只是将最后一颗糖果留在单元格 (1, 1) 处,路径仅包含此单元格。总罚金为:3 + 2 + 2 + 1 = 8。
请注意,Inna 无法使用单元格 (1, 1) 来放置第三个糖果,因为在这种情况下她无法为第四个糖果创建路径。