class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)

        # 1) Compute all window sums
        window_sums = []
        curr_sum = sum(nums[:k])
        window_sums.append(curr_sum)
        for i in range(k, n):
            curr_sum += nums[i] - nums[i - k]
            window_sums.append(curr_sum)
        
        # 2) left[i] = index of best window starting at or before i
        # Use strict > to keep earliest index (lexicographically smallest)
        left = [0] * len(window_sums)
        best = 0
        for i in range(len(window_sums)):
            if window_sums[i] > window_sums[best]:
                best = i
            left[i] = best
        
        # 3) right[i] = index of best window starting at or after i
        # Use >= to prefer earlier on ties
        right = [0] * len(window_sums)
        best = len(window_sums) - 1
        for i in range(len(window_sums) - 1, -1, -1):
            if window_sums[i] >= window_sums[best]:
                best = i
            right[i] = best
        # 4) Try each middle position
        max_total = 0
        result = 0

        for mid in range(k, len(window_sums) - k):
            l = left[mid - k] # Best left window
            r = right[mid + k] # Best right window
            total = window_sums[l] + window_sums[mid] + window_sums[r]

            if total > max_total:
                max_total = total
                result = [l, mid, r]
        return result