홍윤이는 N행 M열의 격자 모양으로 이루어진 캠핑장을 차렸다.

캠핑장의 각 격자 칸에는 바위가 있을 수도 있고 빈 땅일 수도 있다.

홍윤이는 여름 방학 기간 Q일 동안 캠핑장을 운영하려고 하며 그 동안 하루에 한 팀씩 캠핑장에 방문하기로 했다.

Q개의 팀들 중 i번째 날 오는 팀은 x_i행 y_i열의 칸을 거점으로 쓰고 싶다는 요청을 보내왔다.

홍윤이는 각 팀들에 대해 거점 칸을 포함하고 바위를 포함하지 않도록 가능한 한 큰 정사각형 모양의 텐트를 칠 것이다.

(왜 그런 짓을 하는지는 모르겠지만) 바위가 있는 칸을 거점으로 쓰고 싶다는 팀들도 있으며 그 팀은 텐트를 칠 수 없다.

우리가 할 일은 홍윤이를 도와 각 팀들에게 준비될 텐트의 넓이를 미리 알려주는 것이다.

단, 텐트를 칠 수 없는 팀은 넓이를 0으로 한다.

캠핑 timer 2s memory 512MB

캠핑 2s 512MB