Nhận diện gương mặt

Nhận diện gương mặt là một bài toán kinh điển trong lĩnh vực trí tuệ nhân tạo và đang được áp dụng vào nhiều ứng dụng thực tế ngày nay. Một bộ lọc cạnh dùng đặc trưng Haar để nhận diện ra mắt trên mặt người dùng hai hình chữ nhật gọi là vùng trắng $w$ và vùng đen $b$ để quét qua bức ảnh.

Bạn được cho một tấm ảnh hình vuông có kích thước $N\times N$ chứa các điểm ảnh có các giá trị $p$ ($0\le p\le 255$) với gốc tọa độ $(0;0)$ ở góc trái trên, trục $x$ hướng từ trái sang phải, trục $y$ hướng từ trên xuống dưới, và $T$ bộ lọc cạnh, bộ lọc thứ $i$ thể hiện bằng hai hình chữ nhật $w_i$ và $b_i$ (lần lượt là vùng trắng và vùng đen). Mỗi hình chữ nhật thể hiện bằng $4$ con số là tọa độ góc trái trên và góc phải dưới của nó khi đặt lên tấm ảnh. Như vậy $x$ là chỉ số cột (đánh số từ $0$, từ trái sang phải) và $y$ là chỉ số dòng (đánh số từ $0$, từ trên xuống dưới); hình chữ nhật gồm cả các điểm ảnh nằm trên biên của nó.

Đặc trưng Haar thứ $k$ của bộ lọc được tính bằng hiệu của tổng giá trị các điểm ảnh trong vùng trắng thứ $k$ với tổng giá trị các điểm ảnh trong vùng đen thứ $k$:

$$Haa{r}_k=\sum _{p_{i,j}\in (w_k)}{p}_{i,j}-\sum _{p_{x,y}\in (b_k)}{p}_{x,y}$$

Yêu cầu: Cho trước một tấm ảnh và các bộ lọc. Với mỗi bộ lọc, hãy tính đặc trưng Haar tương ứng.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N$ và $T$ lần lượt là kích thước của ảnh và số lượng đặc trưng cần phải tính.
• $N$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên trong khoảng $[0;255]$ là giá trị các điểm ảnh (dòng thứ $y+1$ trong số đó ứng với dòng $y$ của ảnh, số thứ $x+1$ trên dòng ứng với cột $x$).
• $T$ dòng tiếp theo, mỗi dòng là một bộ lọc cạnh dùng để tính các đặc trưng. Bộ lọc $i$ được biểu diễn bằng hai hình chữ nhật $w_i$ và $b_i$, mỗi hình chữ nhật biểu diễn bằng $4$ số nguyên lần lượt là $x_1,y_1,x_2,y_2$ là cặp tọa độ của góc trái trên $(x_1;y_1)$ và góc phải dưới $(x_2;y_2)$, $0\le x_1\le x_2<N$, $0\le y_1\le y_2<N$. Như vậy mỗi dòng gồm $8$ số: $4$ số của $w_i$ rồi $4$ số của $b_i$.

Dữ liệu ra

In ra $T$ số nguyên, mỗi số trên một dòng, là các đặc trưng Haar tương ứng với các bộ lọc được cho trong dữ liệu vào.

Ràng buộc

• $1\le N\le {10}^3$, $1\le T\le 2\times {10}^5$.
• $0\le p\le 255$.
• $0\le x_1\le x_2<N$, $0\le y_1\le y_2<N$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $1\le N\le {10}^2$ và $1\le T\le 2\times {10}^4$.
• Subtask 2 ($30\%$ số điểm): $1\le N\le {10}^3$ và $1\le T\le 5\times {10}^4$.
• Subtask 3 ($40\%$ số điểm): $1\le N\le {10}^3$ và $1\le T\le 2\times {10}^5$.

Ví dụ