class Solution {
    private fun <A, B> product(
        xs: Sequence<A>,
        ys: Sequence<B>,
    ): Sequence<Pair<A, B>> = xs.flatMap { x -> ys.map { y -> x to y } }

    private fun <A, B> product(
        xs: Iterable<A>,
        ys: Iterable<B>,
    ): Sequence<Pair<A, B>> = product(xs.asSequence(), ys.asSequence())

    private enum class State {
        Unguarded,
        Guarded,
        Guard,
        Wall,
    }

    private fun update(
        grid: MutableList<MutableList<State>>,
        y: Int,
        x: Int,
        guarded: Boolean,
    ): Boolean =
        when (grid[y][x]) {
            State.Guard -> true
            State.Wall -> false
            else -> {
                if (guarded) {
                    grid[y][x] = State.Guarded
                }

                guarded
            }
        }

    fun countUnguarded(
        m: Int,
        n: Int,
        guards: Array<IntArray>,
        walls: Array<IntArray>,
    ): Int {
        // Initialize grid
        val grid =
            MutableList(m) {
                MutableList(n) { State.Unguarded }
            }

        // Place guards
        for (guard in guards) {
            val (y, x) = guard[0] to guard[1]
            grid[y][x] = State.Guard
        }

        // Place walls
        for (wall in walls) {
            val (y, x) = wall[0] to wall[1]
            grid[y][x] = State.Wall
        }

        // Process horizontally
        product(0..<m, listOf(0..<n, (0..<n).reversed())).forEach { (y, direction) ->
            direction.fold(false) { isGuardLineActive, x ->
                update(grid, y, x, isGuardLineActive)
            }
        }

        // Process vertically
        product(0..<n, listOf(0..<m, (0..<m).reversed())).forEach { (x, direction) ->
            direction.fold(false) { isGuardLineActive, y ->
                update(grid, y, x, isGuardLineActive)
            }
        }

        return grid.sumOf { row ->
            row.count { it == State.Unguarded }
        }
    }
}