// 演算法（同 C）：按列攤平，平移 k 次 = 每個元素從一維索引 idx 移到 (idx+k)%total。
// Algorithm: flatten row-major; k shifts move flattened index idx to (idx + k) % total.
// One pass over all cells, O(m*n) time.

class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size();          // m 是列數 / number of rows (vector 的元素個數)
        int n = grid[0].size();       // n 是每列行數 / columns per row
        int total = m * n;            // 元素總數 / total number of cells
        k = k % total;                // 只保留有效位移 / keep only the effective shift

        // 建立一個 m x n、全部初始化為 0 的答案網格
        // Make an m x n answer grid, every cell initialized to 0
        // vector<vector<int>> 是「陣列的陣列」，第二個參數給每列的初始內容
        vector<vector<int>> ans(m, vector<int>(n, 0));

        for (int i = 0; i < m; i++) {         // 逐列 / for each row
            for (int j = 0; j < n; j++) {     // 逐格 / for each cell
                int idx = i * n + j;          // 舊的攤平索引 / old flattened index
                int pos = (idx + k) % total;  // 移動後的新索引 / rotated new index
                // pos / n 得到新列、pos % n 得到新行，把值放進去
                // pos / n gives new row, pos % n gives new column; store the value
                ans[pos / n][pos % n] = grid[i][j];
            }
        }
        return ans;                   // 回傳結果，vector 會自動管理記憶體 / vectors free themselves
    }
};