type NumArray struct {
    sums []int
}


func Constructor(nums []int) NumArray {
    sums := make([]int, len(nums))
    sums[0] = nums[0]
    for i := 1; i < len(nums); i++ {
        sums[i] = sums[i-1] + nums[i]
    }
    return NumArray{sums}
}


func (this *NumArray) SumRange(left int, right int) int {
    if left == 0 {
        return this.sums[right] 
    }
    
    return this.sums[right] - this.sums[left-1]
}


/**
 * Your NumArray object will be instantiated and called as such:
 * obj := Constructor(nums);
 * param_1 := obj.SumRange(left,right);
 */

type NumMatrix struct {
    sums [][]int
}


func Constructor(matrix [][]int) NumMatrix {
    sums := make([][]int, len(matrix)+1)
    sums[0] = make([]int, len(matrix[0])+1)
    for i := range matrix {
        sums[i+1] = make([]int, len(matrix[0])+1)

        for j := range matrix[i] {
            sums[i+1][j+1] = sums[i+1][j] + matrix[i][j]
        }
    }
    // fmt.Println(sums)
    for i := range matrix {
        for j := range matrix[i] {
            sums[i+1][j+1] += sums[i][j+1]
        }
    }

    // for i := range sums {
    //     for j := range sums[i] {
    //         fmt.Printf("%2d ", sums[i][j])
    //     }
    //     fmt.Println()
    // }

    return NumMatrix { sums }
}


func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    return this.sums[row2+1][col2+1] - this.sums[row1][col2+1] - this.sums[row2+1][col1]  +  this.sums[row1][col1]
}


/**
 * Your NumMatrix object will be instantiated and called as such:
 * obj := Constructor(matrix);
 * param_1 := obj.SumRegion(row1,col1,row2,col2);
 */

func merge(nums1 []int, m int, nums2 []int, n int)  {
    i, j := m-1, n-1
    p := m+n-1
    for i >= 0 && j >= 0 {
        if nums1[i] >= nums2[j] {
            nums1[p] = nums1[i]
            p--
            i--
        } else {
            nums1[p] = nums2[j]
            p--
            j--
        }
    }
    for i >= 0 {
        nums1[p] = nums1[i]
        p--
        i--
    }
    for j >= 0 {
        nums1[p] = nums2[j]
        p--
        j--
    }
}

func sortedSquares(nums []int) []int {
    n := len(nums)
    i, j := 0, n-1
    result := make([]int, n)
    p := n-1

    for i <= j {
        a := nums[i] * nums[i]
        b := nums[j] * nums[j]
        if a >= b {
            result[p] = a
            p--
            i++
        } else {
            result[p] = b
            p--
            j--
        }
    }
    
    return result
}

func diagonalSort(mat [][]int) [][]int {
    m, n := len(mat), len(mat[0])
    diagonals := make(map[int][]int, m+n-1)

    for i := range mat {
        for j, v := range mat[i] {
            diagonals[j-i] = append(diagonals[j-i], v)
        }
    }

    for _, v := range diagonals {
        sort.Slice(v, func(i, j int) bool {
            return v[i] >= v[j]
        })
    }

    for i := range mat {
        for j := range mat[i] {
            v := diagonals[j-i][len(diagonals[j-i])-1]
            diagonals[j-i] = diagonals[j-i][:len(diagonals[j-i])-1]
            
            mat[i][j] = v
        }
    }

    return mat
}

func shiftGrid(grid [][]int, k int) [][]int {
    m, n := len(grid), len(grid[0])

    total := m*n
    all := make([]int, total)

    for i := range grid {
        for j, v := range grid[i] {
            all[(i*n+j+k) % total] = v
        }
    }

    for i := range grid {
        for j := range grid[i] {
            grid[i][j] = all[i*n+j]
        }
    }

    return grid
}

func shiftGrid(grid [][]int, k int) [][]int {
    m, n := len(grid), len(grid[0])

    k = k % (m*n)

    reverse(grid, 0, m*n-1)
    reverse(grid, 0,k-1)
    reverse(grid, k, m*n-1)

    return grid
}

func reverse(grid [][]int, start, end int) {
    i, j := start, end
    for i < j {
        a := get(grid, i)
        b := get(grid, j)
        set(grid, j, a)
        set(grid, i, b)

        i++
        j--
    }
}

func set(grid [][]int, index int, newValue int) {
    n := len(grid[0])
    i, j := index / n, index % n
    grid[i][j] = newValue
}

func get(grid [][]int, index int) int {
    n := len(grid[0])
    i, j := index / n, index % n
    return grid[i][j]
}