Given a rectangular cake with height h and width w, and two arrays of integers horizontalCuts and verticalCuts where horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut.
Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a huge number, return this modulo 10^9 + 7.
 
Example 1:

Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4 
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green piece of cake has the maximum area.

Example 2:

Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
Output: 6
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green and yellow pieces of cake have the maximum area.

Example 3:
Input: h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
Output: 9

 
Constraints:

2 <= h, w <= 10^9
1 <= horizontalCuts.length < min(h, 10^5)
1 <= verticalCuts.length < min(w, 10^5)
1 <= horizontalCuts[i] < h
1 <= verticalCuts[i] < w
It is guaranteed that all elements in horizontalCuts are distinct.
It is guaranteed that all elements in verticalCuts are distinct.

Difficulty: interview

Starter code:

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        

Solutions:
class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        mod = int(1e9)+7
        return ( ( self.getMax(horizontalCuts, h) % mod ) * ( self.getMax(verticalCuts, w) % mod ) ) % mod
        
    def getMax(self, cuts, size):
        if len(cuts) == 1:
            return max(cuts[0], size - cuts[0])
        
        cuts.sort()
        
        max_cut_size = max(cuts[0], size - cuts[-1])
        for index in range(1, len(cuts)):
            if cuts[index] - cuts[index - 1] > max_cut_size:
                max_cut_size = cuts[index] - cuts[index - 1]
        
        return max_cut_size

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        h_max = self.get_max_interval(w, sorted(verticalCuts))
        w_max = self.get_max_interval(h, sorted(horizontalCuts))
        return (h_max*w_max) % (10**9 + 7)
    
    def get_max_interval(self, length, cuts):
        current = 0
        max_cut = 0
        for cut in cuts:
            max_cut = max(max_cut, cut - current)
            current = cut
        
        max_cut = max(max_cut, length - current)
        return max_cut

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts.sort()
        verticalCuts.sort()
        
        def getGap(arr, n):
            prev=0
            i=0
            res=0
            while i<len(arr):
                res=max(arr[i]-prev, res)
                prev=arr[i]
                i+=1
            return max(n-prev, res)
    
        return (getGap(horizontalCuts, h)*getGap(verticalCuts, w))%(10**9 + 7)

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        n=len(horizontalCuts)
        m=len(verticalCuts)
        A=horizontalCuts[:]
        B=verticalCuts[:]
        A.sort()
        B.sort()
        A.insert(0,0)
        B.insert(0,0)
        A.append(h)
        B.append(w)
        

        maxw=0
        maxh=0
        
        for i in range(1,n+2):
            maxh=max(maxh,A[i]-A[i-1])
            
        for i in range(1,m+2):
            maxw=max(maxw,B[i]-B[i-1])
    

            
        m=10**9+7
        
        return ((maxw%m)*(maxh%m))%m
            
            
            
        
        
        


class Solution:
    def maxArea(self, h: int, w: int, hc: List[int], v: List[int]) -> int:
        hc.append(0)
        hc.append(h)
        v.append(0)
        v.append(w)
        v.sort()
        hc.sort()
        max_v = max_h = 0
        for i in range(1,len(hc)):
            max_h = max(max_h,hc[i]-hc[i-1])
        for i in range(1,len(v)):
            max_v = max(max_v,v[i]-v[i-1])
        return max_h*max_v% 1000000007

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts = sorted(horizontalCuts)
        verticalCuts = sorted(verticalCuts)
        
        horizontalCuts.insert(0, 0)
        horizontalCuts.append(h)
        verticalCuts.insert(0,0)
        verticalCuts.append(w)
        
        print(horizontalCuts)
        print(verticalCuts)
        
        maxx = 0
        for x in range(1, len(horizontalCuts)):
            maxx = max(maxx, horizontalCuts[x] - horizontalCuts[x-1])
            
        maxy = 0
        for y in range(1, len(verticalCuts)):
            maxy = max(maxy, verticalCuts[y] - verticalCuts[y-1])
            
        return (maxx * maxy)%1000000007

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        # def get_max_length(length: int, cuts: List[int]) -> int:
        #     cuts.sort()
        #     max_length = max(cuts[0], length - cuts[-1])
        #     for i in range(1, len(cuts)):
        #         max_length = max(max_length, cuts[i] - cuts[i-1])
        #     return max_length
        return self.get_max_length(h, horizontalCuts) * self.get_max_length(w, verticalCuts) % 1000000007

    def get_max_length(self, length: int, cuts: List[int]) -> int:
        if len(cuts) == 1:
            return max(cuts[0], length - cuts[0])
        
        cuts.sort()
        max_length = max(cuts[0], length - cuts[-1])
        for i in range(1, len(cuts)):
            max_length = max(max_length, cuts[i] - cuts[i - 1])
        return max_length

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        if 0 not in horizontalCuts:
            horizontalCuts.append(0)
        if h not in horizontalCuts:
            horizontalCuts.append(h)
        if 0 not in verticalCuts:
            verticalCuts.append(0)
        if w not in verticalCuts:
            verticalCuts.append(w)
        horizontalCuts.sort()
        verticalCuts.sort()
        i = 0
        max_diff = -float('inf')
        while i in range(len(horizontalCuts)-1):
            if horizontalCuts[i+1]-horizontalCuts[i] > max_diff:
                max_diff = max(max_diff, horizontalCuts[i+1]-horizontalCuts[i])
            i += 1
        j = 0
        max_diff1 = -float('inf')
        while j in range(len(verticalCuts)-1):
            if verticalCuts[j+1] - verticalCuts[j] > max_diff1:
                max_diff1 = max(max_diff1, verticalCuts[j + 1] - verticalCuts[j])
            j += 1
        return (max_diff*max_diff1)%((10**9)+7)

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        # def get_max_length(length: int, cuts: List[int]) -> int:
        #     cuts.sort()
        #     max_length = max(cuts[0], length - cuts[-1])
        #     for i in range(1, len(cuts)):
        #         max_length = max(max_length, cuts[i] - cuts[i-1])
        #     return max_length
        mod = int(1e9) + 7
        return (self.get_max_length(h, horizontalCuts) % mod) * (self.get_max_length(w, verticalCuts) % mod) % mod

    def get_max_length(self, length: int, cuts: List[int]) -> int:
        if len(cuts) == 1:
            return max(cuts[0], length - cuts[0])
        
        cuts.sort()
        max_length = max(cuts[0], length - cuts[-1])
        for i in range(1, len(cuts)):
            # max_length = max(max_length, cuts[i] - cuts[i - 1])
            if cuts[i] - cuts[i - 1] > max_length:
                max_length = cuts[i] - cuts[i - 1]
        return max_length

class Solution:
    def maxArea(self, h: int, w: int, hh: List[int], vv: List[int]) -> int:
        hh = sorted(hh) + [h]
        vv = sorted(vv) + [w]
        prev = 0
        hm = 0
        for i in hh:
            hm = max(hm,i-prev)
            prev = i
        prev = 0
        vm = 0
        for i in vv:
            vm = max(vm,i-prev)
            prev = i
        return (vm * hm)  % (10**9 + 7)
        


class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        # def get_max_length(length: int, cuts: List[int]) -> int:
        #     cuts.sort()
        #     max_length = max(cuts[0], length - cuts[-1])
        #     for i in range(1, len(cuts)):
        #         max_length = max(max_length, cuts[i] - cuts[i-1])
        #     return max_length
        mod = int(1e9) + 7
        return (self.get_max_length(h, horizontalCuts) % mod) * (self.get_max_length(w, verticalCuts) % mod) % mod

    def get_max_length(self, length: int, cuts: List[int]) -> int:
        if len(cuts) == 1:
            return max(cuts[0], length - cuts[0])
        
        cuts.sort()
        max_length = max(cuts[0], length - cuts[-1])
        for i in range(1, len(cuts)):
            max_length = max(max_length, cuts[i] - cuts[i - 1])
        return max_length

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        # def get_max_length(length: int, cuts: List[int]) -> int:
        #     cuts.sort()
        #     max_length = max(cuts[0], length - cuts[-1])
        #     for i in range(1, len(cuts)):
        #         max_length = max(max_length, cuts[i] - cuts[i-1])
        #     return max_length
        return self.get_max_length(h, horizontalCuts) * self.get_max_length(w, verticalCuts) % 1000000007

    def get_max_length(self, length: int, cuts: List[int]) -> int:
        cuts.sort()
        max_length = max(cuts[0], length - cuts[-1])
        for i in range(1, len(cuts)):
            max_length = max(max_length, cuts[i] - cuts[i - 1])
        return max_length

class Solution:
    def maxArea(self, h: int, w: int, hc: List[int], vc: List[int]) -> int:
        hc, vc = [0] + sorted(hc) + [h], [0] + sorted(vc) + [w]
        return max(hc[i] - hc[i-1] for i in range(1, len(hc))) * max(vc[i] - vc[i-1] for i in range(1, len(vc))) % 1000000007

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        mod = 10**9 + 7
        horizontalCuts.extend([0, h])
        horizontalCuts.sort()
        verticalCuts.extend([0, w])
        verticalCuts.sort()
        hor_max = 0
        for i in range(len(horizontalCuts)-1):
            hor_max = max(hor_max, horizontalCuts[i+1] - horizontalCuts[i])
        
        ver_max = 0
        for i in range(len(verticalCuts)-1):
            ver_max = max(ver_max, verticalCuts[i+1] - verticalCuts[i])
        return (hor_max*ver_max)%mod
       
                


class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:

        new_horizontal_cuts = [0] + sorted(horizontalCuts) +[h]
        new_vertical_cuts = [0] + sorted(verticalCuts) +[w]
        mod = int(1e9)+7
        max_height = 0
        max_width = 0
        for j in range(len(new_vertical_cuts)-1):
            if max_width < new_vertical_cuts[j+1]-new_vertical_cuts[j]:
                max_width = new_vertical_cuts[j+1]-new_vertical_cuts[j]
        for i in range(len(new_horizontal_cuts)-1):
            if max_height< new_horizontal_cuts[i+1]-new_horizontal_cuts[i]:
                max_height = new_horizontal_cuts[i+1]-new_horizontal_cuts[i]
        
        return (max_width*max_height)%mod
            


class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        mod = 10**9 + 7
        horizontalCuts += [0, h]
        horizontalCuts.sort()
        verticalCuts += [0, w]
        verticalCuts.sort()
        hor_max = 0
        for i in range(len(horizontalCuts)-1):
            hor_max = max(hor_max, abs(horizontalCuts[i] - horizontalCuts[i+1]))
        
        ver_max = 0
        for i in range(len(verticalCuts)-1):
            ver_max = max(ver_max, abs(verticalCuts[i] - verticalCuts[i+1]))
        return (hor_max*ver_max)%mod
       
                


class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        def get_max_length(length: int, cuts: List[int]) -> int:
            if len(cuts) == 1:
                return max(cuts[0], length - cuts[0])

            cuts.sort()
            max_length = max(cuts[0], length - cuts[-1])
            for i in range(1, len(cuts)):
                # max_length = max(max_length, cuts[i] - cuts[i - 1])
                if cuts[i] - cuts[i - 1] > max_length:
                    max_length = cuts[i] - cuts[i - 1]
            return max_length

        return get_max_length(h, horizontalCuts) * get_max_length(w, verticalCuts) % 1000000007

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
#         def get_max_length(length: int, cuts: List[int]) -> int:
#             if len(cuts) == 1:
#                 return max(cuts[0], length - cuts[0])

#             cuts.sort()
#             max_length = max(cuts[0], length - cuts[-1])
#             for i in range(1, len(cuts)):
#                 # max_length = max(max_length, cuts[i] - cuts[i - 1])
#                 if cuts[i] - cuts[i - 1] > max_length:
#                     max_length = cuts[i] - cuts[i - 1]
#             return max_length

        return self.get_max_length(h, horizontalCuts) * self.get_max_length(w, verticalCuts) % 1000000007

    def get_max_length(self, length: int, cuts: List[int]) -> int:
        if len(cuts) == 1:
            return max(cuts[0], length - cuts[0])

        cuts.sort()
        max_length = max(cuts[0], length - cuts[-1])
        for i in range(1, len(cuts)):
            # max_length = max(max_length, cuts[i] - cuts[i - 1])
            if cuts[i] - cuts[i - 1] > max_length:
                max_length = cuts[i] - cuts[i - 1]
        return max_length

class Solution:
    def maxArea(self, h: int, w: int, hori: List[int], verti: List[int]) -> int:
        hori.sort()
        verti.sort()
        x = hori[0]
        for i in range(1, len(hori)):
            x = max(x, hori[i]-hori[i-1])
        x = max(x, h - hori[-1])
        y = verti[0]
        for i in range(1, len(verti)):
            y = max(y, verti[i]-verti[i-1])
        y = max(y, w - verti[-1])
        return (x*y)%1000000007


class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalStrips = [0] + sorted(horizontalCuts) + [h]
        verticalStrips = [0] + sorted(verticalCuts) + [w]
        
        maxW = max([horizontalStrips[i + 1] - horizontalStrips[i] for i in range(len(horizontalStrips) - 1)])
        maxH = max([verticalStrips[i + 1] - verticalStrips[i] for i in range(len(verticalStrips) - 1)])
        
        return (maxW * maxH) % ((10 ** 9) + 7)

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:

        new_horizontal_cuts = [0] + sorted(horizontalCuts) +[h]
        new_vertical_cuts = [0] + sorted(verticalCuts) +[w]

        max_area = 0
        mod = int(1e9)+7
        max_height = 0
        max_width = 0
        for j in range(len(new_vertical_cuts)-1):
            if max_width < new_vertical_cuts[j+1]-new_vertical_cuts[j]:
                max_width = new_vertical_cuts[j+1]-new_vertical_cuts[j]
        for i in range(len(new_horizontal_cuts)-1):
            if max_height< new_horizontal_cuts[i+1]-new_horizontal_cuts[i]:
                max_height = new_horizontal_cuts[i+1]-new_horizontal_cuts[i]
        
        return (max_width*max_height)%mod
            


class Solution:
    
    
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        # Return ans % (1E9 + 7)
        # A = ((vi+1) - vi)*(hi+1 - hi)
        
        def getMaxSpace(cuts, upperLimit):
            cuts = sorted(cuts)
            if not any(cuts):
                return upperLimit
            
            ans = cuts[0] # first piece is 0 to first cut
            for i in range(len(cuts)-1):
                ans = max(ans, cuts[i+1] - cuts[i])
            return max(ans, upperLimit - cuts[-1])
        
        maxHorSpace = getMaxSpace(horizontalCuts, h)
        maxVertSpace = getMaxSpace(verticalCuts, w)
        
        mod = 1E9+7
        return int((maxHorSpace * maxVertSpace) % mod)


class Solution:
    def getMax(self, max: int, cuts: List[int]) -> int:
        last = 0
        for x in cuts:
            cur = x - last
            if cur > max:
                max = cur
            last = x
        return max
    
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        mod = 1000000007
        horizontalCuts.sort()
        verticalCuts.sort()
        maxh = self.getMax(h - horizontalCuts[-1], horizontalCuts)
        maxv = self.getMax(w - verticalCuts[-1], verticalCuts)
        
        return maxh%mod * maxv%mod


class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts.append(0)
        horizontalCuts.append(h)
        
        verticalCuts.append(0)
        verticalCuts.append(w)
        
        horizontalCuts.sort()
        verticalCuts.sort()
        
        mw = 0
        mh = 0
        
        for x, y in zip(horizontalCuts, horizontalCuts[1:]):
            mw = max(mw, y-x)
        for x, y in zip(verticalCuts, verticalCuts[1:]):
            mh = max(mh, y-x)
        mod = 10**9 + 7
        return (mw * mh) % mod

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
#         m = 0
#         horizontalCuts.sort()
#         verticalCuts.sort()
#         numHoriz = len(horizontalCuts)
#         numVert = len(verticalCuts)
#         prevH = 0
#         for horiz in range(numHoriz + 1):
#             prevV = 0
#             for vert in range(numVert + 1):
#                 if horiz == numHoriz:
#                     currH = h
#                 else: 
#                     currH = horizontalCuts[horiz]
#                 if vert == numVert:
#                     currV = w
#                 else:
#                     currV = verticalCuts[vert]
#                 m = max(m, (currH - prevH) * (currV - prevV))
                
                
#                 prevV = currV
#             prevH = currH
                
#         return m % (10**9 + 7)
        horizontalCuts.sort()
        verticalCuts.sort()
        prev = 0
        hDiff = 0
        for horiz in horizontalCuts:
            hDiff = max(hDiff, horiz - prev)
            prev = horiz
            
        hDiff = max(h - prev, hDiff)
        
        prev = 0 
        vDiff = 0
        for vert in verticalCuts:
            vDiff = max(vDiff, vert - prev)
            prev = vert
        vDiff = max(w - prev, vDiff)
        
        return (vDiff * hDiff) % (10**9 + 7)

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        
        horizontalCuts.append(h)
        verticalCuts.append(w)
        
        def get_max_gap(array):
            array.sort()
            max_hor_width = array[0]
            for previous_cut, next_cut in zip(array, array[1:]):  
                max_hor_width = max(max_hor_width, next_cut - previous_cut)
                
            return max_hor_width

        return (get_max_gap(horizontalCuts) * get_max_gap(verticalCuts)) % 1000000007
    
# time complexity - nlogn - mainly sorting
# sub1: corner case for 0, n index
# sub2: result should be module
#  does insertion take extra time? - maybe just O(n) - could be avoided with smart comparison


class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts.sort()
        verticalCuts.sort()
        max_h,max_w=max(horizontalCuts[0],h-horizontalCuts[-1]),max(verticalCuts[0],w-verticalCuts[-1])
        for i in range(1,len(horizontalCuts)):
            max_h=max(max_h,horizontalCuts[i]-horizontalCuts[i-1])
        for j in range(1,len(verticalCuts)):
            max_w=max(max_w,verticalCuts[j]-verticalCuts[j-1])
        return (max_w*max_h)%(10**9+7)             


class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        
        horizontalCuts.append(h)
        verticalCuts.append(w)
        
        def get_max_gap(array):
            array.sort()
            max_hor_width = array[0]
            for previous_cut, next_cut in zip(array, array[1:]):  
                max_hor_width = max(max_hor_width, next_cut - previous_cut)
            return max_hor_width

        return (get_max_gap(horizontalCuts) * get_max_gap(verticalCuts)) % 1000000007
    
# time complexity - nlogn - mainly sorting
# sub1: corner case for 0, n index
# sub2: result should be module
#  does insertion take extra time? - maybe just O(n) - could be avoided with smart comparison


from typing import List
import numpy

import sys
# Definition for a binary tree node.
# Definition for a binary tree node.
class Solution:
  def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
    horizontalCuts.insert(0, 0)
    horizontalCuts.append(h)
    horizontalCuts.sort()

    verticalCuts.insert(0, 0)
    verticalCuts.append(w)
    verticalCuts.sort()

    maxh = -1
    maxv = -1

    for index, value in enumerate(horizontalCuts):
      if index == 0:
        continue
      maxh = max(maxh, value - horizontalCuts[index-1])

    for index, value in enumerate(verticalCuts):
      if index == 0:
        continue
      maxv = max(maxv, value - verticalCuts[index-1])

    module = int(pow(10, 9) + 7)
    result = maxv * maxh % module
    return result

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts.sort()
        verticalCuts.sort()
        mx= max(verticalCuts[0], w - verticalCuts[-1])
        my = max(horizontalCuts[0], h - horizontalCuts[-1])
        for i in range(1,len(verticalCuts)):
            mx=max(mx,verticalCuts[i] - verticalCuts[i - 1])
        for i in range(1,len(horizontalCuts)):
            my = max(my, horizontalCuts[i] - horizontalCuts[i - 1])              
        return mx*my%(10**9+7)

class Solution:
    def maxArea(self, h, w, horizontalCuts, verticalCuts):
        H = [0] + horizontalCuts + [h]
        W = [0] + verticalCuts + [w]
        H.sort()
        W.sort()

        hmax, wmax = 0, 0
        for i in range(1, len(H)):
            hmax = max(hmax, H[i] - H[i - 1])

        for i in range(1, len(W)):
            wmax = max(wmax, W[i] - W[i - 1])

        return hmax * wmax % 1000000007

class Solution:
    
    
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        # Return ans % (1E9 + 7)
        # A = ((vi+1) - vi)*(hi+1 - hi)
        
        def getMaxSpace(cuts, upperLimit):
            #cuts = sorted(cuts)
            cuts.sort()
            if not any(cuts):
                return upperLimit
            
            
            ans = cuts[0] # first piece is 0 to first cut
            for i in range(len(cuts)-1):
                ans = max(ans, cuts[i+1] - cuts[i])
            return max(ans, upperLimit - cuts[-1])
        
        maxHorSpace = getMaxSpace(horizontalCuts, h)
        maxVertSpace = getMaxSpace(verticalCuts, w)
        
        mod = 1E9+7
        return int((maxHorSpace * maxVertSpace) % mod)


class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts.sort()
        verticalCuts.sort()
        max_h = max(horizontalCuts[0], h - horizontalCuts[-1])
        if len(horizontalCuts) > 1:
            for i in range(len(horizontalCuts)-1):
                if max_h < abs(horizontalCuts[i+1] - horizontalCuts[i]):
                        max_h = abs(horizontalCuts[i+1] - horizontalCuts[i])
        
        max_v = max(verticalCuts[0], w - verticalCuts[-1])
        if len(verticalCuts) > 1:
            for i in range(len(verticalCuts)-1):
                if max_v < abs(verticalCuts[i+1] - verticalCuts[i]):
                        max_v = abs(verticalCuts[i+1] - verticalCuts[i])
        
        return ((max_h % (10**9 + 7)) * (max_v % (10**9 + 7))) % (10**9 + 7)
            


class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts.sort()
        verticalCuts.sort()
         
        def maxDelta(cuts, end):
            cuts.sort()
            cuts.append(end)
            cuts.append(0)

            md=0
            for i in range(len(cuts)-1):
                md=max(md,cuts[i]-cuts[i-1])
            
            return md
        

        return (maxDelta(horizontalCuts, h)*maxDelta(verticalCuts, w))%(10**9 + 7)

        
        mh=maxDelta(horizontalCuts, h)
        mv=maxDelta(verticalCuts, w)
        
        return (mh*mv)%(10^9+7)

class Solution:
    def maxArea(self, h: int, w: int, hCuts: List[int], vCuts: List[int]) -> int:
        hCuts.sort()
        vCuts.sort()
        H, V = max(hCuts[0], h - hCuts[-1]), max(vCuts[0], w - vCuts[-1])
        for i in range(1, len(hCuts)):
            H = max(H, hCuts[i] - hCuts[i - 1])
        for i in range(1, len(vCuts)):
            V = max(V, vCuts[i] - vCuts[i - 1])
        return H * V % 1000000007

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts.sort()
        verticalCuts.sort()
        def helper(ll,num):
            '''
            ll is a sorted list
            num is either h or w
            '''
            ll.append(num)
            ans = ll[0]
            for i in range(1,len(ll)):
                if ll[i]-ll[i-1] > ans:
                    ans = ll[i]-ll[i-1]
            return ans
       
        
        return int((helper(horizontalCuts,h) * helper(verticalCuts,w))%(1e9+7))

         
        


class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts = [0] + sorted(horizontalCuts) + [h]
        verticalCuts = [0] + sorted(verticalCuts) + [w]
        new_h = max([horizontalCuts[i+1]-horizontalCuts[i] for i in range(len(horizontalCuts)-1)])
        new_w = max([verticalCuts[i+1]-verticalCuts[i] for i in range(len(verticalCuts)-1)])
        return (new_h * new_w) % (10 ** 9 +7) 

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        modu = 1000000007
        
        # horizontal- i
        # vertical-j
        # 横向记录0-x, x-y, y-m留下最大
        # 竖向也一样
        
        h_max = 0
        v_max = 0
        
        horizontalCuts.append(0)
        horizontalCuts.append(h)
        
        verticalCuts.append(0)
        verticalCuts.append(w)
        
        horizontalCuts.sort()
        verticalCuts.sort()
        
        for i in range(1,len(horizontalCuts)):
            h_max = max(h_max, horizontalCuts[i]-horizontalCuts[i-1])
        
        for j in range(1,len(verticalCuts)):
            v_max = max(v_max, verticalCuts[j]-verticalCuts[j-1])
        
        return (v_max*h_max)%modu

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts.sort()
        verticalCuts.sort()
        max_h = horizontalCuts[0]
        for h_cut in range(1, len(horizontalCuts)):
            max_h = max(max_h, horizontalCuts[h_cut] - horizontalCuts[h_cut-1])
        max_h = max(max_h, h - horizontalCuts[-1])
        max_v = verticalCuts[0]
        for v_cut in range(1, len(verticalCuts)):
            max_v = max(max_v, verticalCuts[v_cut] - verticalCuts[v_cut-1])
        max_v = max(max_v, w - verticalCuts[-1])
        return max_h * max_v % int(1e9 + 7)

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts.sort()
        verticalCuts.sort()
        max_hor_width = horizontalCuts[0]
        for i in range(len(horizontalCuts)-1):  
            max_hor_width = max(max_hor_width, horizontalCuts[i+1]-horizontalCuts[i])
        max_hor_width = max(max_hor_width, h-horizontalCuts[len(horizontalCuts)-1])

        max_vert_width = verticalCuts[0]
        for i in range(len(verticalCuts)-1):
            max_vert_width = max(max_vert_width, verticalCuts[i+1]-verticalCuts[i])
        max_vert_width = max(max_vert_width, w-verticalCuts[len(verticalCuts)-1])
        
        return (max_vert_width * max_hor_width) % 1000000007
# time complexity - nlogn - mainly sorting
# sub1: corner case for 0, n index
# sub2: result should be module
#  does insertion take extra time? - maybe just O(n) - could be avoided with smart comparison


class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        
        horizontalCuts.sort()
        verticalCuts.sort()
        
        ph, pw = 0, 0
        msh, msw = 0, 0
        
        for ch in horizontalCuts:
            if ch - ph > msh:
                msh = ch-ph
            ph = ch
        if h - ph > msh:
            msh = h - ph
            
        for cw in verticalCuts:
            if cw - pw > msw:
                msw = cw - pw
            pw = cw
        if w - pw > msw:
            msw = w - pw
            
        return msh*msw%(10**9 + 7)
        
            
        
        
        
        
        
        
        
        


class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts.sort()
        verticalCuts.sort()
        print(horizontalCuts, verticalCuts)
        pre = 0
        hori_max = 0
        for i, cut in enumerate(horizontalCuts):
            hori_max = max(hori_max, cut - pre)
            pre = cut
        
        hori_max = max(hori_max, h - pre)
        #print(hori_max)
        pre = 0
        vert_max = 0
        for i, cut in enumerate(verticalCuts):
            vert_max = max(vert_max, cut - pre)
            pre = cut
        
        vert_max = max(vert_max, w - pre)
        #print(vert_max)
        return (hori_max * vert_max) % (10**9 + 7)

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        ver = [0] + sorted(verticalCuts) + [w]
        hor = [0] + sorted(horizontalCuts) + [h]
        
        dh = max(hor[i] - hor[i-1] for i in range(1, len(hor)))
        dv = max(ver[i] - ver[i-1] for i in range(1, len(ver)))
        
        return dh*dv % (10**9 + 7)

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        h_max = self.get_max_interval(w, sorted(verticalCuts))
        w_max = self.get_max_interval(h, sorted(horizontalCuts))
        
        print(h_max, w_max)
        
        return (h_max*w_max) % (10**9 + 7)
    
    def get_max_interval(self, length, cuts):
        current = 0
        max_cut = 0
        for cut in cuts:
            max_cut = max(max_cut, cut - current)
            current = cut
        
        max_cut = max(max_cut, length - current)
        return max_cut

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalStrips = [0] + sorted(horizontalCuts) + [h]
        verticalStrips = [0] + sorted(verticalCuts) + [w]
        
        maxStripWidth = max([horizontalStrips[i + 1] - horizontalStrips[i] for i in range(len(horizontalStrips) - 1)])
        maxStripHeight = max([verticalStrips[i + 1] - verticalStrips[i] for i in range(len(verticalStrips) - 1)])
        
        return (maxStripWidth * maxStripHeight) % ((10 ** 9) + 7)

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
#         m = 0
#         horizontalCuts.sort()
#         verticalCuts.sort()
#         numHoriz = len(horizontalCuts)
#         numVert = len(verticalCuts)
#         prevH = 0
#         for horiz in range(numHoriz + 1):
#             prevV = 0
#             for vert in range(numVert + 1):
#                 if horiz == numHoriz:
#                     currH = h
#                 else: 
#                     currH = horizontalCuts[horiz]
#                 if vert == numVert:
#                     currV = w
#                 else:
#                     currV = verticalCuts[vert]
#                 m = max(m, (currH - prevH) * (currV - prevV))
                
                
#                 prevV = currV
#             prevH = currH
                
#         return m % (10**9 + 7)
        horizontalCuts.sort()
        verticalCuts.sort()
        prev = 0
        hDiff = 0
        for horiz in horizontalCuts:
            print(horiz, prev, horiz - prev)
            hDiff = max(hDiff, horiz - prev)
            prev = horiz
            
        hDiff = max(h - prev, hDiff)
        
        prev = 0 
        vDiff = 0
        for vert in verticalCuts:
            vDiff = max(vDiff, vert - prev)
            prev = vert
        vDiff = max(w - prev, vDiff)
        print(vDiff, hDiff)
        
        return (vDiff * hDiff) % (10**9 + 7)

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts.sort()
        verticalCuts.sort()
        max_width = verticalCuts[0]
        max_height = horizontalCuts[0]
        for i in range(len(horizontalCuts) - 1):
            max_height = max(max_height, (horizontalCuts[i+1] - horizontalCuts[i]))
        max_height = max(max_height, (h - horizontalCuts[-1]))

        for i in range(len(verticalCuts)-1):
            max_width = max(max_width, (verticalCuts[i+1] - verticalCuts[i]))
        max_width = max(max_width, (w - verticalCuts[-1]))
        return (max_height * max_width) % (10**9 + 7)

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts.append(0)
        horizontalCuts.append(h)
        horizontalCuts.sort()
        Maxh = max([horizontalCuts[i] - horizontalCuts[i-1] for i in range(1,len(horizontalCuts))])
        verticalCuts.append(0)
        verticalCuts.append(w)
        verticalCuts.sort()
        Maxv = max([verticalCuts[i] - verticalCuts[i-1] for i in range(1,len(verticalCuts))])
        
        return Maxh*Maxv % 1000000007

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts, verticalCuts = sorted([0, h]+horizontalCuts), sorted([0, w]+verticalCuts)
        return max([after-prev for after, prev in zip(horizontalCuts[1:], horizontalCuts)])*max([after-prev for after, prev in zip(verticalCuts[1:], verticalCuts)])%(10**9+7)

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts.sort()
        verticalCuts.sort()
         
        def maxDelta(cuts, end):
            cuts.sort()
            cuts.append(end)
            cuts.append(0)

            md=0
            for i in range(len(cuts)-1):
                md=max(md,cuts[i]-cuts[i-1])
            
            return md
        
        def getGap(arr, n):
            prev=0
            i=0
            res=0
            while i<len(arr):
                res=max(arr[i]-prev, res)
                prev=arr[i]
                i+=1
            return max(n-prev, res)
    
        return (maxDelta(horizontalCuts, h)*maxDelta(verticalCuts, w))%(10**9 + 7)

        
        mh=maxDelta(horizontalCuts, h)
        mv=maxDelta(verticalCuts, w)
        
        return (mh*mv)%(10^9+7)

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts.sort()
        verticalCuts.sort()
        hr=[0]+horizontalCuts+[h]
        vr=[0]+verticalCuts+[w]
        hmax,vmax=0,0
        for i in range(1,len(hr)):
            hmax=max(hmax,hr[i]-hr[i-1])
        for i in range(1,len(vr)):
            vmax=max(vmax,vr[i]-vr[i-1])
        return (hmax*vmax)%(10**9+7)