各位观众，各位观众，您现在收看的是第 666 届跳蚤奥运会的比赛现场。在刚刚的跳高比赛中，天才跳高小将“最强跳蚤”靠着“最强跳蚤跳跳跳”和经验丰富的伏特跳蚤国王大战了三天三夜，最后战成 $233:233$ 平。考虑到迟迟不能决出胜者，比赛组委会决定临时更换比赛项目，而被选中的则是在跳蚤大陆流行已久的游戏——五子棋。

五子棋是 Picks 博士发明的一款益智类游戏。为了加大难度，这里的五子棋实则是 “$k$ 子棋”。

游戏规则很简单，游戏双方分别使用黑白两色的棋子，下在 $n\times m$ 的棋盘上，先形成 $k$ 子连成一条直线的一方获胜。即，若己方有连续的 $k$ 个棋子形成方向为上下、左右、左上右下、左下右上四个方向之一的直线，就可以获得胜利。

但没想到的是，“最强跳蚤”和伏特跳蚤国王不仅跳得比谁都高，知识水平也是不相上下。啊我们看到，在第 66 局他们再一次打成了平局……

现在是我们的有奖竞猜环节！大家可以来猜猜下一个平局是怎么产生的呢？最早给出答案的观众可以获得小火车一列哦。

现在，你作为一名观众想参与到竞猜环节中。但首先，你需要构造一个下棋过程使得填满整个棋盘之后也没有连续 $k$ 个同色棋子在这四个方向上排成一条直线。

注意，$n\times m$ 可能为奇数，此时先手会比后手多下一步棋。

输入格式

第一行三个正整数 $n,m,k$，意义如前所述。

输出格式

如果双方不能打成平局，输出 $-1$；

否则输出 $n\times m$ 行，第 $i$ 行两个整数 $x_i,y_i$ 表示第 $i$ 次落子的坐标为第 $x_i$ 行第 $y_i$ 列。黑子先行，所以 $i$ 为奇数时为黑方落子，$i$ 为偶数时白方落子。坐标需满足 $1\le x_i\le n,1\le y_i\le m$。

样例一

input

4 4 3

output

1 2
1 1
1 4
1 3
2 1
2 3
2 2
2 4
3 3
3 2
3 4
3 1
4 1
4 4
4 3
4 2

explanation

样例一的参考输出最终得到的棋盘如下：

1 0 1 0
0 0 1 1
1 1 0 0
0 1 0 1

其中 0 为先手，1 为后手。

样例二

input

2 3 3

output

1 1
2 1
2 2
1 2
1 3
2 3

限制与约定

由于一些原因，本题使用捆绑测试。每个子任务有若干个测试点，分为 $4$ 个子任务，你只有通过一个子任务的所有测试点才能得到这个子任务的分数。

在所有数据中，都满足 $1\le k\le {10}^9$ 且 $1\le n,m\le 500$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载