require "table2"
local fmt = require "fmt"

local count <const> = {0}
local dir <const> = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}}

local function walk(y, x, h, w, grid, len, nxt)
    if y == 0 or y == h or x == 0 or x == w then
        count[1] += 2
        return
    end
    local t = y * (w + 1) + x
    grid[t + 1] += 1
    grid[len - t + 1] += 1
    for i = 1, 4 do
        if grid[t + nxt[i] + 1] == 0 then
            walk(y + dir[i][1], x + dir[i][2], h, w, grid, len, nxt)
        end
    end
    grid[t + 1] -= 1
    grid[len - t + 1] -= 1
end

local function cutrectangle(hh, ww, recur)
    local h, w
    if hh % 2 != 0 then
        h, w = ww, hh
    else
        h, w = hh, ww
    end
    if h % 2 != 0 then
        return 0
    elseif w == 1 then
        return 1
    elseif w == 2 then
        return h
    elseif h == 2 then
        return w
    end
    local cy = h // 2
    local cx = w // 2
    local len = (h + 1) * (w + 1)
    local grid = table.rep(len, 0)
    len -= 1
    local nxt = {-1, -w - 1, 1, w + 1}
    if recur then count[1] = 0 end
    for x = cx + 1, w - 1 do
        local t = cy * (w + 1) + x
        grid[t + 1] = 1
        grid[len - t + 1] = 1
        walk(cy - 1, x, h, w, grid, len, nxt)
    end
    count[1] += 1
    if h == w then
        count[1] *= 2
    elseif w % 2 == 0 and recur then
        cutrectangle(w, h, false)
    end
    return count[1]
end

for y = 1, 10 do
    for x = 1, y do
        if x % 2 == 0 or y % 2 == 0 then
            fmt.print($"%2d x %2d: %d", y, x, cutrectangle(y, x, true))
        end
    end
end