当你正在解决 ICPC 问题时，你虚构的女朋友被邪恶的 ALU 绑架了，你必须在为时已晚之前救出她！ALU 把她关在一个大小为 $n \times m$ 的迷宫中。你的旅程从 $(1, 1)$ 开始，而你虚构的女朋友被关在 $(n, m)$。

然而，邪恶的 ALU 知道你会来，并在迷宫中设置了许多致命的陷阱。但你并非毫无准备，因为你已经掌握了解决问题的艺术。通过一些简单的观察，你发现只要你按照国际象棋中马的走法移动，并且从不重复访问同一个位置，陷阱就不会伤害到你。

但还有一个重要的问题：时间。你虚构的女朋友是一个有着双马尾的可爱萝莉，最近对你的感情产生了一些傲娇的特质。只有当你恰好在 $t$ 秒时赶到救她，你才能成功打动她。你必须考虑到这一点。走一步马步恰好花费 1 秒，你在 0 时刻位于 $(1, 1)$。

现在是时候制定计划，从邪恶手中救出她了！

输入格式

第一行包含三个正整数 $n, m, t$ ($8 \le n, m \le 500, n+m \le t \le \frac{3}{4}nm$)。保证 $t$ 的奇偶性与 $n+m$ 的奇偶性相同。

输出格式

输出 $t$ 行，每行包含两个正整数。第 $i$ 行（从 1 开始计数）的坐标对表示你在时刻 $i$ 所处的位置。输出应当是从 $(1, 1)$ 到 $(n, m)$ 的合法路径，因此第 $t$ 行应当是 $n \ m$。每一次移动都必须是合法的马步，且没有任何坐标超出迷宫范围或出现超过一次。

样例

样例输入 1

8 8 16

样例输出 1

3 2
4 4
2 3
3 5
5 6
7 7
8 5
6 6
8 7
6 8
7 6
8 4
6 5
8 6
6 7
8 8