Let ~(i, j)~ denote the ~j^\text{th}~ square in the ~i^\text{th}~ row of the park.

Let ~dp1[i][j]~ be the sum of ~l^l~ for all rectangles where ~(i, j)~ is the bottom right corner of the rectangle. Let ~dp2[i][j]~ be the sum of ~w \cdot l^l~ for the same rectangles. Let ~h[i][j]~ be the smallest number such that ~(i-h, j)~ is blocked or outside the grid. Let ~k~ be the largest number smaller than ~j~ such that ~h[i][k] \le h[i][j]~. To find this ~k~ for each ~(i, j)~ in amortized ~\mathcal O(1)~, a stack may be used.

Consider a rectangle which has its bottom left corner before or at the ~k^\text{th}~ column and bottom right corner at ~(i, j)~. Then this is a unique rectangle with its bottom right corner at ~(i, k)~ with its right side stretched to the ~j^\text{th}~ column. The length of this rectangle remains unchanged but its width increases by a certain amount, specifically ~j-k~. As such, the sum of ~l^l~ for rectangles with their bottom left corner before or at the ~k^\text{th}~ column is ~dp1[i][k]~ and the sum of ~w \cdot l^l~ is ~dp2[i][k]+(j-k) \cdot dp1[i][k]~.

Now consider the rectangles with their bottom left corner after the ~k^\text{th}~ column and bottom right corner at ~(i, j)~. Since ~k~ is the largest number smaller than ~j~ such that ~h[i][k] \le h[i][j]~, any rectangle with height from ~1~ to ~h[i][k]~ and width from ~1~ to ~j-k~ can have their bottom right corner at ~(i, j)~ and still fit. In fact, these are all the rectangles with their bottom left corner after the ~k^\text{th}~ column and bottom right corner at ~(i, j)~. The sum of ~l^l~ and ~w \cdot l^l~ in this case can be computed in ~\mathcal O(1)~ if the sum of ~1^1+2^2+\dots+n^n~ for all ~1 \le n \le \max(M, N)~ has been precomputed.

To compute the final values of ~dp1[i][j]~ and ~dp2[i][j]~, take the sum of the corresponding results found in each case. So using this ~dp~ relation, all ~dp1~ and ~dp2~ values for a single row can be computed in ~\mathcal O(N)~. All the ~dp~ values can be computed in ~\mathcal O(MN)~.

To find the sums of all ~lw(l^l+w^w)~, perform this algorithm and then rotate the grid and repeat the algorithm. The final answer is the sum of all the ~dp2~ values.

Time Complexity: ~\mathcal O(MN)~