VBOARD - Bàn cờ

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Cho một bàn cờ vua kích thước nxn, trên mỗi ô của bàn cờ có ghi một con số. Biết ô trên trái của bàn cờ vua là ô trắng (các ô của bàn cờ vua có dạng xen kẽ trắng đen). Các cột được đánh số từ 1 đến n từ trái sang phải, các hàng được đánh số từ 1 đến n từ trên xuống dưới. Ô ở hàng i, cột j của bàn cờ được ký hiệu là ô (i, j).

Cuội đưa ra những câu đố cho Bờm như sau: Cuội sẽ cho Bờm biết các vùng hình chữ nhật trên bàn cờ, nhiệm vụ của Bờm là phải tính giá trị tuyệt đối của độ chênh lệch giữa tổng giá trị các ô trắng và tổng giá trị các ô đen trên vùng hình chữ nhật đó. Bạn hãy lập trình giúp Bờm trả lời các câu đố của Cuội.

Dữ liệu

  • Dòng đầu tiên: chứa số nguyên n (1 ≤ n ≤ 500).
  • Dòng thứ i trong số n dòng tiếp theo chứa n số nguyên a i1 , a i2 , ..., a ij , cho biết các số trên hàng i của bàn cờ (0 ≤ a ij < 100).
  • Dòng thứ n+2: chứa số q, cho biết số câu đố của Cuội (1 ≤ q ≤ 10000).
  • q dòng tiếp theo, mỗi dòng chứa 4 số nguyên i 1 , j 1 , i 2 , j 2 cho biết các tọa độ của vùng hình nhật trong một câu đố của Cuội: tọa độ đỉnh trái trên là (i 1 , j 1 ) và đỉnh dưới phải là (i 2 , j 2 ).

Kết quả

In ra q dòng, mỗi dòng cho biết đáp án của Bờm đối với câu đố tương ứng của Cuội.

Giới hạn

Có 50% số test, tương ứng với 50% số điểm, trong đó 1 ≤ n ≤ 100 và 1 ≤ q ≤ 2000.

Ví dụ

Dữ liệu
3 
1 3 5
2 4 6
0 10 5
2
1 1 2 2
1 2 3 3

Kết quả
0
5

  • Người up: paulmcvn
  • Nguồn bài: VNOI Marathon '08 - Round 2/DivBProblem Setter: Ngô Minh Ðức