// 演算法：把二維網格按列攤平成一條長度 total=m*n 的直線，
// 一次平移 = 這條線向右循環一格；平移 k 次 = 每個元素移到 (idx+k)%total。
// Algorithm: flatten row-major; one shift = right cyclic shift by 1,
// so k shifts send flattened index idx to (idx + k) % total. One pass, O(m*n).

int** shiftGrid(int** grid, int gridSize, int* gridColSize, int k,
                int* returnSize, int** returnColumnSizes) {
    int m = gridSize;              // m 是列數（幾橫排）/ m = number of rows
    int n = gridColSize[0];        // n 是行數（每列幾格）/ n = columns per row
    int total = m * n;             // total 是元素總數 / total number of cells
    k = k % total;                 // 移動 total 格會回到原狀，只留有效位移 / effective shift only

    // 配置回傳用的二維陣列：先要 m 個 int* 的陣列（每個指向一列）
    // Allocate the answer: an array of m row-pointers (int*)
    int** ans = (int**)malloc(sizeof(int*) * m);
    // returnColumnSizes 要回傳每一列的長度，也需要 m 個 int 的陣列
    // returnColumnSizes reports each row's length; needs m ints
    *returnColumnSizes = (int*)malloc(sizeof(int) * m);

    for (int i = 0; i < m; i++) {          // 逐列配置與設定長度 / set up each row
        ans[i] = (int*)malloc(sizeof(int) * n);  // 每列 n 個 int / n ints per row
        (*returnColumnSizes)[i] = n;             // 告訴 LeetCode 這列有 n 格 / this row has n cols
    }
    *returnSize = m;               // 回傳的網格有 m 列 / the returned grid has m rows

    // 掃過每一個元素，直接算出它的新位置並填入 / place each cell at its shifted spot
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int idx = i * n + j;           // 攤平後的舊一維索引 / old flattened index
            int pos = (idx + k) % total;   // 循環移動後的新一維索引 / new index after rotation
            int newRow = pos / n;          // 折回列座標：整除得列 / unfold row = pos / n
            int newCol = pos % n;          // 折回行座標：取餘得行 / unfold col = pos % n
            ans[newRow][newCol] = grid[i][j];  // 把值搬到新位置 / copy value to its new cell
        }
    }
    return ans;                    // 回傳新網格 / return the new grid
}