def matrixRotation(matrix, r):
    m = len(matrix)
    n = len(matrix[0])
    d = dict() # storing matrix coordinates and their values
    for i in range(min(m, n) // 2):
        # storing the coordinates for each loop or layer of the matrix
        loop = [(i, j) for j in range(i, n - i)] # top side
        loop += [(j, n - i - 1) for j in range(i + 1, m - i)] # right side
        loop += [(m - i - 1, j) for j in range(n - i - 2, i - 1 , -1)] # bottom side
        loop += [(j, i) for j in range(m - i - 2, i , -1)] # left side
        # listing the values of each loop of the matrix, then shift to mimic the effect of rotation
        loop_values = [matrix[r][c] for r, c in loop]
        rotated_values = loop_values[r % len(loop_values):] + loop_values[: r % len(loop_values)]
        # storing the new values of every position of the loop to respective coordinates
        for k in range(len(loop)):
            d[loop[k]] = rotated_values[k]
    # print out the resultant matrix
    for r in range(m):
        line = [d[(r, c)] for c in range(n)]
        print(*line)

sub rotate_matrix {
    my ($matrix, $r) = @_;
    my $rows = scalar @$matrix;
    my $cols = scalar @{$matrix->[0]};
    
    my $num_layers = int(min($rows, $cols) / 2);
    
    for my $layer (0 .. $num_layers - 1) {
        my @ring = extract_ring($matrix, $layer, $rows, $cols);
        my $perimeter = scalar @ring;

        my $effective_r = $r % $perimeter;
        @ring = (@ring[$effective_r .. $#ring], @ring[0 .. $effective_r - 1]);
        
        place_ring($matrix, \@ring, $layer, $rows, $cols);
    }
}

sub extract_ring {
    my ($matrix, $layer, $rows, $cols) = @_;
    my @ring;

    for my $i ($layer .. $cols - $layer - 1) {
        push @ring, $matrix->[$layer][$i];
    }

    for my $i ($layer + 1 .. $rows - $layer - 1) {
        push @ring, $matrix->[$i][$cols - $layer - 1];
    }

    for my $i (reverse $layer .. $cols - $layer - 2) {
        push @ring, $matrix->[$rows - $layer - 1][$i];
    }

    for my $i (reverse $layer + 1 .. $rows - $layer - 2) {
        push @ring, $matrix->[$i][$layer];
    }

    return @ring;
}

sub place_ring {
    my ($matrix, $ring_ref, $layer, $rows, $cols) = @_;
    my @ring = @$ring_ref;
    my $index = 0;

    for my $i ($layer .. $cols - $layer - 1) {
        $matrix->[$layer][$i] = $ring[$index++];
    }

    for my $i ($layer + 1 .. $rows - $layer - 1) {
        $matrix->[$i][$cols - $layer - 1] = $ring[$index++];
    }

    for my $i (reverse $layer .. $cols - $layer - 2) {
        $matrix->[$rows - $layer - 1][$i] = $ring[$index++];
    }

    for my $i (reverse $layer + 1 .. $rows - $layer - 2) {
        $matrix->[$i][$layer] = $ring[$index++];
    }
}

sub matrixRotation {
    my ($matrix, $r) = @_;
    
    rotate_matrix($matrix, $r);    
    foreach my $row (@$matrix) {
        print "@$row\n";
    }
}

sub min {
    return $_[0] < $_[1] ? $_[0] : $_[1];
}

void matrixRotation(vector<vector<int>> matrix, int r) {
    int mr = matrix.size();
    int mc = matrix[0].size();
    int dirx[4] = {0, 1, 0, -1}; // x, y
    int diry[4] = {1, 0, -1, 0};
    vector<vector<int>>ring; // drul
    int num_ring = min(ceil(mr / 2), ceil(mc / 2));
    for(int i = 0; i < num_ring; i++){
        int sx = i, sy = i;
        int dir = 0, current_ring_num = 2 * mc + 2 * mr - 8 * i - 4;
        vector<int> tmp;
        for(int j = 0; j < current_ring_num; j++){
            if(sx + dirx[dir] >= mc - i || sy + diry[dir] >= mr - i || sy + diry[dir] < i){
                dir++;
            }
            tmp.push_back(matrix[sy][sx]);
            sx += dirx[dir];
            sy += diry[dir];
        }
        rotate(tmp.begin(), tmp.end() - r % current_ring_num, tmp.end());
        ring.push_back(tmp);
    }
    for(int i = 0; i < ring.size(); i++){
        int sx = i, sy = i;
        int dir = 0, current_ring_num = 2 * mc + 2 * mr - 8 * i - 4;
        for(int j = 0; j < current_ring_num; j++){
            if(sx + dirx[dir] >= mc - i || sy + diry[dir] >= mr - i || sy + diry[dir] < i){
                dir++;
            }
            matrix[sy][sx] = ring[i][j];
            sx += dirx[dir];
            sy += diry[dir];
        }
    }
    for(int i = 0; i < matrix.size(); i++){
        for(int j = 0; j < matrix[i].size(); j++)
            cout<<matrix[i][j]<<" ";
        cout<<endl;
    }
}

void matrixRotation(std::vector<std::vector<int>> matrix, int r)
{
    std::vector<std::vector<int>> res = matrix;
    /* Max number of iterations needed to rotate every layer in the 2d vector */
    uint16_t maxIterations = std::min(matrix.size(), matrix[0].size()) / 2;
    for (int iteration = 0; iteration < maxIterations; iteration++) {
        /* Limit of looping through each layer */
        int32_t row = matrix.size() - 2 * iteration, rowIterator = iteration;
        int32_t col = matrix[0].size() - 2 * iteration, colIterator = iteration;
        int perimeter = (2 * (row + col) - 4), tempRot = r;
        r = r % perimeter; // Removing redundant rotations
        int loopAround = 0;
        /* Top side of the current layer */
        while (loopAround < r && colIterator < col + iteration) {
            loopAround++, colIterator++;
        }
        if (colIterator - iteration >= col) {
            loopAround--, colIterator--;
        }
        /* Right side of the current layer */
        while (loopAround < r && rowIterator < row + iteration) {
            loopAround++, rowIterator++;
        }
        if (rowIterator - iteration >= row) {
            loopAround--, rowIterator--;
        }
        /* Bottom side of the current layer */
        while (loopAround < r && colIterator >= iteration) {
            loopAround++, colIterator--;
        }
        if (colIterator < iteration) {
            loopAround--, colIterator++;
        }
        /* Left side of the current layer */
        while (loopAround < r && rowIterator >= iteration) {
            loopAround++, rowIterator--;
        }
        if (rowIterator < iteration) {
            loopAround--, rowIterator++;
        }
        /* Now we have the location of the element to start the rotation from at matrix[rowIterator][colIterator] */
        /* Top side of the current layer except last element */
        for (int layerCol = iteration; layerCol < col + iteration - 1; layerCol++) {
            res[iteration][layerCol] = matrix[rowIterator][colIterator];
            if (rowIterator == iteration && colIterator < col + iteration - 1 && colIterator >= iteration) {
                colIterator++;
            } else if (colIterator == col + iteration - 1 && rowIterator < row + iteration - 1 && rowIterator >= iteration) {
                rowIterator++;
            } else if (rowIterator == row + iteration - 1 && colIterator <= col + iteration - 1 && colIterator > iteration) {
                colIterator--;
            } else if (colIterator == iteration && rowIterator <= row + iteration - 1 && rowIterator > iteration) {
                rowIterator--;
            }
        }
        /* Right side of the current layer except last element */
        for (int layerRow = iteration; layerRow < row + iteration - 1; layerRow++) {
            res[layerRow][col + iteration - 1] = matrix[rowIterator][colIterator];
            if (rowIterator == iteration && colIterator < col + iteration - 1 && colIterator >= iteration) {
                colIterator++;
            } else if (colIterator == col + iteration - 1 && rowIterator < row + iteration - 1 && rowIterator >= iteration) {
                rowIterator++;
            } else if (rowIterator == row + iteration - 1 && colIterator <= col + iteration - 1 && colIterator > iteration) {
                colIterator--;
            } else if (colIterator == iteration && rowIterator <= row + iteration - 1 && rowIterator > iteration) {
                rowIterator--;
            }
        }
        /* Bottom side of the current layer except last element */
        for (int layerCol = col + iteration - 1; layerCol > iteration; layerCol--) {
            res[row + iteration - 1][layerCol] = matrix[rowIterator][colIterator];
            if (rowIterator == iteration && colIterator < col + iteration - 1 && colIterator >= iteration) {
                colIterator++;
            } else if (colIterator == col + iteration - 1 && rowIterator < row + iteration - 1 && rowIterator >= iteration) {
                rowIterator++;
            } else if (rowIterator == row + iteration - 1 && colIterator <= col + iteration - 1 && colIterator > iteration) {
                colIterator--;
            } else if (colIterator == iteration && rowIterator <= row + iteration - 1 && rowIterator > iteration) {
                rowIterator--;
            }
        }
        /* Left side of the current layer except last element */
        for (int layerRow = row + iteration - 1; layerRow > iteration; layerRow--) {
            res[layerRow][iteration] = matrix[rowIterator][colIterator];
            if (rowIterator == iteration && colIterator < col + iteration - 1 && colIterator >= iteration) {
                colIterator++;
            } else if (colIterator == col + iteration - 1 && rowIterator < row + iteration - 1 && rowIterator >= iteration) {
                rowIterator++;
            } else if (rowIterator == row + iteration - 1 && colIterator <= col + iteration - 1 && colIterator > iteration) {
                colIterator--;
            } else if (colIterator == iteration && rowIterator <= row + iteration - 1 && rowIterator > iteration) {
                rowIterator--;
            }
        }
        r = tempRot;
    }

    for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix[0].size(); j++) {
            std::cout << matrix[i][j] << " ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[0].size(); j++) {
            std::cout << res[i][j] << " ";
        }
        std::cout << std::endl;
    }
}

const matrixPrinter = (matrix: number[][]): void => {
    matrix.forEach(row => console.log(row.join(' ')));
}
function matrixRotation(matrix: number[][], r: number): void {
    /**
     * the size of the maxtrix at circle 1
     */
    const bound_y = matrix.length
    const bound_x = matrix[0].length

    /**
     * read matrix and bind it to [hmap] to easy calculate/reposition after
     */
    let hmap: { [cordinate: string]: number } = {}
    matrix.forEach((row, y) => row.forEach((cell, x) => {
        // counting [c], the circle indexed, start from 1
        let c = 1
        while (true) {
            if (y + 1 == c || y + 1 == bound_y - c + 1) break
            if (x + 1 == c || x + 1 == bound_x - c + 1) break
            c++
        }

        hmap[`${x + 1}:${y + 1}:${c}`] = cell;
    }))

    /**
     * calculate/reposition each number in [hmap]
     * 
     * + [hmap_temp] create to holding reposition number, avoid to override value
     * + [x],[y] is cordinate of number
     * + [v] is the number
     * + [c] is the circle index where the number is in (from outside to inside, start from 1)
     * + [rc] is the remaining rotations of the circle [c]
     * 
     * Q: why each number have [c] and [rc]?
     * A: cause each number can be on different circle, different circle will need different 
     *    number of [r] to complete fully rotation
     * 
     * Q: why [rc] look so complicated?
     * A: the hour hand at 10AM today and 10AM tomorow is the same. we dont need to calculate 
     *    the between. save resources and time.
     *      
     *      EG: with input [r]=20 and matrix [5x4], we have 2 circle to calculate
     *        
     *      circle 1 
     *      moves to complete fully circe: (5 - 1) * 2 + (4 - 1) * 2 = 14
     *      moves we need to real calculate: 20 % 14 = 6
     * 
     *      circle 2 (the size reduce from 5x4 to 3x2, -2 from each side)
     *      moves to complete fully circe: (3 - 1) * 2 + (2 - 1) * 2 = 6
     *      moves we need to real calculate: 20 % 6 = 2
     */
    let hmap_temp: typeof hmap = {}
    Object.keys(hmap).forEach(key => {
        let x = Number(key.split(':')[0]);
        let y = Number(key.split(':')[1]);
        let c = Number(key.split(':')[2]);
        let v = Number(hmap[key]);

        let c_size = { x: bound_x - (c - 1) * 2, y: bound_y - (c - 1) * 2 }
        let c_rotations = r % ((c_size.x - 1) * 2 + (c_size.y - 1) * 2)

        while (c_rotations > 0) {
            let direction: 'up' | 'down' | 'left' | 'right'

            // calculate move direction (for number on the edge) ...
            if (x == c) direction = 'down'
            if (x == bound_x - c + 1) direction = 'up'
            if (y == c) direction = 'left'
            if (y == bound_y - c + 1) direction = 'right'

            // calculate move direction (for number on the corner) ...
            if (x == c && y == c) direction = 'down'
            if (x == c && y == bound_y - c + 1) direction = 'right'
            if (x == bound_x - c + 1 && y == bound_y - c + 1) direction = 'up'
            if (x == bound_x - c + 1 && y == c) direction = 'left'

            // this is why using [hmap] is easyer, just change [x] and [y] to move the number
            switch (direction) {
                case 'up': y--; break
                case 'down': y++; break
                case 'left': x--; break
                case 'right': x++; break
            }

            c_rotations--
        }

        // store number and it new cordinate to new [hmap]
        hmap_temp[`${x}:${y}`] = v
    })

    // now we got new [hmap] stored rotated matrix info, print it
    matrixPrinter(
        new Array(bound_y).fill(0).map((row, y) =>
            new Array(bound_x).fill(0).map((_, x) =>
                hmap_temp[`${x + 1}:${y + 1}`]
            )
        )
    );
}