Задачка

[nick_marcevich2]

Given a rectangular grid of N*M (1-based indexing) in which their are k monsters on k different cells. Now we need to answer Q queries in which we will be given lowest row number(L) and highest row number(H) we need to tell maximum area of rectangle between those rows that don't have a monster. (Here area of rectangle means count of cells only)

Example: Say we have a grid of 4*5 (mean n=4 and m=5) and monsters are located on 7(=k) cells which are (1,3), (1,4), (2,1), (2,4), (3,2), (4,1), (4,2) and let we have 1 query in which L=3 and H=4 then the maximum area is 6 here.

Now if the queries are very large say 10^6...