"""Original static 2D integral grid, half-open queries and all rectangle oracles."""
from itertools import combinations_with_replacement,product
import json

def prefix(grid):
 if type(grid) is not list or not 1<=len(grid)<=6 or any(type(r) is not list or not 1<=len(r)<=6 for r in grid) or len({len(r) for r in grid})!=1 or any(type(v) is not int or abs(v)>10**6 for r in grid for v in r):raise ValueError('rectangular1..6 exact integer grid abs<=1e6')
 h=len(grid);w=len(grid[0]);p=[[0]*(w+1) for _ in range(h+1)]
 for y in range(h):
  for x in range(w):p[y+1][x+1]=grid[y][x]+p[y][x+1]+p[y+1][x]-p[y][x]
 return p

def query(p,y0,y1,x0,x1):
 h=len(p)-1;w=len(p[0])-1
 if any(type(v) is not int for v in [y0,y1,x0,x1]) or not 0<=y0<=y1<=h or not 0<=x0<=x1<=w:raise ValueError('half-open ordered in-bounds integer rectangle')
 return p[y1][x1]-p[y0][x1]-p[y1][x0]+p[y0][x0]

def verify_all(grid):
 p=prefix(grid);h=len(grid);w=len(grid[0]);rows=[]
 for y0,y1 in combinations_with_replacement(range(h+1),2):
  for x0,x1 in combinations_with_replacement(range(w+1),2):
   actual=query(p,y0,y1,x0,x1);expected=sum(sum(r[x0:x1]) for r in grid[y0:y1]);assert actual==expected;rows.append({'rows':[y0,y1],'cols':[x0,x1],'sum':actual})
 for y,x in product(range(h+1),range(w+1)):assert p[y][x]==sum(grid[i][j] for i in range(y) for j in range(x))
 return p,rows

def demo():
 grid=[[1,2,3,4],[5,6,7,8],[9,10,11,12]];p,rows=verify_all(grid);assert len(rows)==150 and query(p,1,3,1,4)==54
 changed=[r[:] for r in grid];changed[1][1]+=10;newp,newrows=verify_all(changed);stale=query(p,1,3,1,4);fresh=query(newp,1,3,1,4);assert stale==54 and fresh==64
 neg=[[-2,0,3],[4,-5,1]];np,nrows=verify_all(neg)
 rejected=[]
 for label,fn in [('empty',lambda:prefix([])),('ragged',lambda:prefix([[1],[1,2]])),('bool_pixel',lambda:prefix([[True]])),('float_pixel',lambda:prefix([[1.0]])),('over_dimension',lambda:prefix([[0]*7])),('reversed_rectangle',lambda:query(p,2,1,0,1)),('out_of_bounds',lambda:query(p,0,4,0,1)),('bool_boundary',lambda:query(p,False,1,0,1))]:
  try:fn()
  except ValueError:rejected.append(label)
  else:raise AssertionError('expected rejection')
 return {'grid':grid,'zero_padded_prefix':p,'main_rectangle':{'rows':[1,3],'cols':[1,4],'sum':54,'wrong_only_prefix_bottom_right':p[3][4]},'all150_rectangles':rows,'negative_grid':{'grid':neg,'prefix':np,'all_rectangles':nrows},'changed_pixel_stale_counterexample':{'row':1,'col':1,'increment':10,'stale':stale,'rebuild_fresh':fresh},'invalid_cases_rejected':rejected,'scope':'static Python-int grid with no fixed-width overflow; preprocessing O(HW) plus padded memory, four-lookup query distinct; no OpenCV/image/OCR/rotated integral/live update or benchmark claim'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))