JYY, a knight of the JSOI kingdom, has returned home after defeating an evil dragon. King JS intends to marry his princess to JYY, but the young and brave JYY must first pass the princess's test.

JYY enters an $N \times M$ underground maze, starting at the top-left corner with coordinates $(1, 1)$. The exit of the maze is at the bottom-right corner with coordinates $(N, M)$.

As a true knight, JYY can only move in the maze according to the rules of a knight in international chess (an "L" shape). Furthermore, he must never visit the same cell twice, and he cannot move outside the boundaries of the maze.

To pass the princess's test, he must reach the exit of the maze in exactly $T$ steps. Please help him plan his route.

Input

The input consists of a single line containing three positive integers $N$, $M$, and $T$, describing the size of the maze and the required number of steps.

Output

Output exactly $T$ lines, each containing two integers $X_i$ and $Y_i$, representing the position reached at the $i$-th step. You may output any valid action plan. The input is guaranteed to have a solution.

Examples

Input 1

8 8 16

Output 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

Constraints