Output the following grid as \(A\):

000000 ... 000000
001111 ... 111110
011111 ... 111110
000000 ... 000000

Let \(B\) be the number of \(1\)s (\(=2W-5\)). We split the grid into an inner cycle (\(B\) 1s and one 0) and an outer cycle (\(2W+4\) 0s).

Let \(N=qB+r\ (0\leq r\lt B)\). Cutting the inner cycle at an appropriate point and unrolling it (so that the 0 is at position \(r+1\)) produces a sequence with inversion count \(r\). Cutting the outer cycle just next to where we cut the inner cycle and connecting the two to form one large cycle, then unrolling this large cycle at an appropriate point (at distance \(q\) from the junction of the two cycles) increases the inversion count by \(qB\), yielding a binary sequence with inversion count \(N\).

With this method, \(0\leq N\leq 999975\) is achievable.

(Implementation example)

H, W, Q = map(int, input().split())
print("0" * W)
print("00" + "1" * (W - 3) + "0")
print("0" + "1" * (W - 2) + "0")
print("0" * W)

inner = [(1, i) for i in range(1, W - 1)] + [(2, i) for i in range(W - 2, 0, -1)]
outer = [(1, 0), (2, 0)] + [(3, i) for i in range(W)] + [(2, W - 1), (1, W - 1)] + [(0, i) for i in range(W - 1, -1, -1)]
B = 2 * W - 5


def dist(p, q):
    return abs(p[0] - q[0]) + abs(p[1] - q[1])


for _ in range(Q):
    N = int(input())
    q = N // B
    r = N % B
    ans_inner = inner[-r:] + inner[:-r]
    for i in range(len(outer)):
        if dist(ans_inner[0], outer[i - 1]) == dist(ans_inner[-1], outer[i]) == 1:
            ans_outer = outer[i:] + outer[:i]
            ans = ans_outer[q:] + ans_inner + ans_outer[:q]
            for x, y in ans:
                print(x + 1, y + 1)
            break