Torus

A regular polygon has all sides of the same length and all interior angles equal. A regular tiling of the Euclidean plane covers the whole plane with congruent regular polygons that do not overlap and meet vertex to vertex. Only three regular polygons admit a regular tiling: the square, the equilateral triangle and the regular hexagon. A lattice is an infinite graph whose drawing on the plane is a regular tiling, so there are the square lattice, the triangular lattice and the hexagonal lattice.

Such a lattice turns into a graph with finitely many vertices and edges that keeps the symmetry of the infinite one. The finite graph can be drawn on the surface of a torus with no edge crossings, and the regions bounded by its shortest cycles have similar shapes and sizes. A graph obtained this way is a toroidal lattice, defined as follows.

Definition 1. Let $m$ and $n$ be integers with $m \ge 3$ and $n \ge 3$. The vertex set of the $m \times n$ toroidal square lattice is $\{v_{i,j} : 0 \le i \le m-1,\ 0 \le j \le n-1\}$. Two vertices $v_{i,j}$ and $v_{i',j'}$ are joined by an edge when one of the following holds.

• $i' = i$ and $j' \equiv j+1 \pmod{n}$
• $j' = j$ and $i' \equiv i+1 \pmod{m}$

Definition 2. Let $m$ and $n$ be integers with $m \ge 3$, $n \ge 3$ and $m$ even. The $m \times n$ toroidal triangular lattice is the $m \times n$ toroidal square lattice together with the following edges, for all $i$ and $j$.

• If $i$ is even, join $v_{i,j}$ and $v_{i',j'}$, where $i' \equiv i+1 \pmod{m}$ and $j' \equiv j-1 \pmod{n}$.
• If $i$ is odd, join $v_{i,j}$ and $v_{i',j'}$, where $i' \equiv i+1 \pmod{m}$ and $j' \equiv j+1 \pmod{n}$.

Definition 3. Let $m$ and $n$ be integers with $m \ge 4$, $n \ge 4$ and both even. The vertex set of the $m \times n$ toroidal hexagonal lattice is $\{v_{i,j} : 0 \le i \le m-1,\ 0 \le j \le n-1\}$. Two vertices $v_{i,j}$ and $v_{i',j'}$ are joined by an edge when one of the following holds.

• $j' = j$ and $i' \equiv i+1 \pmod{m}$
• $i' = i$ and $j' \equiv j+1 \pmod{n}$ and $i+j \equiv 0 \pmod{2}$

To help a project that builds a library of lattice graph algorithms, write a program that finds a cycle visiting every vertex of a given $m \times n$ toroidal lattice exactly once. A cycle is a sequence $(u_1, u_2, \dots, u_{mn})$ of $mn$ distinct vertices such that $u_k$ and $u_{k+1}$ are adjacent for every $k \in \{1, \dots, mn-1\}$, and $u_{mn}$ and $u_1$ are adjacent as well. The toroidal square lattice is simple, so only the toroidal triangular and toroidal hexagonal lattices appear in the input.

The first line contains the number of test cases $T$, a positive integer. Each of the next $T$ lines contains three integers $m$, $n$ and $p$ separated by spaces, with $3 \le m \le 111$, $3 \le n \le 111$ and $p \in \{3, 6\}$. The graph of that test case is the $m \times n$ toroidal triangular lattice if $p = 3$, and the $m \times n$ toroidal hexagonal lattice if $p = 6$.

The given lattice always satisfies its definition: $m$ is even when $p = 3$, and both $m$ and $n$ are even and at least 4 when $p = 6$.

Print the results for the $T$ test cases in the given order. For each test case, the first line contains an integer that tells whether a cycle exists: 1 if it does, -1 if it does not. Only when the first line is 1, it is followed by $mn$ lines listing the vertices of the cycle in order. Print vertex $v_{i,j}$ as (i,j), with no space or tab inside a line.

Several cycles can exist, so only the cycle built by the following rule is accepted. Below, $a \bmod b$ is the remainder in the range from $0$ to $b-1$.

For $p = 3$, print in this order.

1. $v_{0,0}$
2. For $j = 0, 1, \dots, n-1$ in this order: print $v_{1,j}, v_{2,j}, \dots, v_{m-1,j}$ if $j$ is even, and $v_{m-1,j}, v_{m-2,j}, \dots, v_{1,j}$ if $j$ is odd.
3. $v_{0,n-1}$
4. $v_{0,n-2}, v_{0,n-3}, \dots, v_{0,1}$

For $p = 6$, for $k = 0, 1, \dots, n/2-1$ in this order, print these $2m$ vertices.

1. $v_{(1-t) \bmod m,\ 2k}$ for $t = 0, 1, \dots, m-1$
2. $v_{(2+t) \bmod m,\ 2k+1}$ for $t = 0, 1, \dots, m-1$

This rule produces a cycle for every input that satisfies the constraints, so the first line of each test case is always 1.