Cho một bảng hình chữ nhật A gồm n×m ô vuông, trên mỗi ô vuông chứa 1 số nguyên, các dòng được đánh số trên xuống dưới bắt đầu từ 1, các cột được đánh số từ trái qua phải cũng bắt đầu từ 1. Mỗi số trong bảng có giá trị tuyệt đối không vượt quá 10000.

Yêu cầu: Hãy tính tổng tất cả các phần tử trên bảng hình chữ nhật đó.

Dữ liệu vào:

• Dòng đầu chứa 2 số nguyên dương n,m (n,m ≤2000).
• Dòng thứ i trong n dòng tiếp theo chứa m số nguyên lần lượt ứng với các phần tử nằm trên dòng thứ i của bảng A.

Dữ liệu ra:

• Ghi một số nguyên là tổng các phần tử trên bảng.

Ví dụ

Input

5 6
1 2 3 1 9 3
2 2 6 7 6 5
3 6 3 8 12 1
1 7 8 1 3 0
9 6 12 3 4 2

Output

136

Cho một bảng hình chữ nhật A gồm n×m ô vuông, trên mỗi ô vuông chứa 1 số nguyên, các dòng được đánh số trên xuống dưới bắt đầu từ 1, các cột được đánh số từ trái qua phải cũng bắt đầu từ 1. Mỗi số trong bảng có giá trị tuyệt đối không vượt quá 10000.

Yêu cầu: Hãy tìm và in ra phần tử lớn nhất trên bảng hình chữ nhật đó.

Dữ liệu vào:

• Dòng đầu chứa 2 số nguyên dương n,m (n,m≤2000).
• Dòng thứ i trong n dòng tiếp theo chứa m số nguyên lần lượt ứng với các phần tử nằm trên dòng thứ i của bảng A.

Dữ liệu ra:

• Ghi một số nguyên là phần tử lớn nhất tìm được.

Ví dụ

Input

5 6
1 2 3 1 9 3
2 2 6 7 6 5
3 6 3 8 12 1
1 7 8 1 3 0
9 6 12 3 4 2

Output

12

Cho một bảng hình chữ nhật A gồm n×m ô vuông, trên mỗi ô vuông chứa 1 số nguyên, các dòng được đánh số trên xuống dưới bắt đầu từ 1, các cột được đánh số từ trái qua phải cũng bắt đầu từ 1. Mỗi số trong bảng có giá trị tuyệt đối không vượt quá 10000.

Yêu cầu: Hãy tìm hàng có tổng lớn nhất và in ra tổng tìm được.

Dữ liệu vào:

• Dòng đầu chứa 2 số nguyên dương n,m (n,m≤2000).
• Dòng thứ i trong n dòng tiếp theo chứa m số nguyên lần lượt ứng với các phần tử nằm trên dòng thứ i của bảng A.

Dữ liệu ra:

• Gồm 1 số nguyên duy nhất là kết quả bài toán.

Ví dụ

Input

5 6
1 2 3 1 9 3
2 2 6 7 6 5
3 6 3 8 12 1
1 7 8 1 3 0
9 6 12 3 4 2

Output

36

Cho lưới ô vuông ~A~ kích thước ~N~ x ~N~. Các dòng được đánh số 1 đến ~N~ từ trên xuống dưới, các cột được đánh số 1 đến ~N~ từ trái qua phải. Ô nằm trên giao giữa dòng ~i~ và cột ~j~ được gọi là ô (~i,j~) và trên đó có ghi một số nguyên dương ~A_{ij}~ (~1 ≤ i, j ≤ N~).

Yêu cầu: Hãy lập trình chọn một ô vuông con có kích thước ~K~ x ~K~ có tổng giá trị của tất cả các ô của hình vuông con là lớn nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên dương ~N~, ~K~ (~N ≤ 10^3~, ~K ≤ N~).

• Dòng thứ i trong số ~N~ dòng tiếp theo chứa ~N~ số nguyên dương, số thứ j là ~A_{ij}~ (~A_{ij} ≤ 10^3~)

Dữ liệu ra:

• Một số nguyên dương là tổng giá trị lớn nhất theo yêu cầu đề ra.

Ví dụ:

Input

4 3 
1 9 1 1 
9 9 9 9 
1 9 9 9 
1 9 9 14 

Output

86

Ràng buộc:

• Có 70% số test ~N<10~ và ~k<10~.
• Có 30% test còn lại không có ràng buộc gì thêm

Cho một hình vuông A gồm n×n ô vuông, trên mỗi ô vuông chứa 1 số nguyên(n≤1000), các dòng được đánh số trên xuống dưới bắt đầu từ 1, các cột được đánh số từ trái qua phải cũng bắt đầu từ 1. Mỗi số trong bảng có giá trị tuyệt đối không vượt quá 10000. Đường chéo chính của bảng là đường thẳng nối hai ô (1,1) và(n,n).

Yêu cầu: Hãy tính tổng các ô nằm trên đường chéo chính.

Dữ liệu vào:

• Dòng đầu chứa số n.
• Dòng thứ i trong n dòng tiếp theo chứa n số nguyên lần lượt ứng với các phần tử nằm trên dòng thứ i của bảng A.

Dữ liệu ra:

• Ghi một số nguyên duy nhất là kết quả bài toán trên.

Ví dụ:

Input

4
1 2 3 4
4 3 2 0
0 2 3 4
1 4 5 6

Output

13

Cho một hình vuông A gồm n×n ô vuông, trên mỗi ô vuông chứa 1 số nguyên(n≤1000), các dòng được đánh số trên xuống dưới bắt đầu từ 1, các cột được đánh số từ trái qua phải cũng bắt đầu từ 1. Mỗi số trong bảng có giá trị tuyệt đối không vượt quá 10000. Đường chéo phụ của bảng là đường thẳng nối hai ô (n,1) và(1,n).

Yêu cầu: Hãy tính tổng các ô nằm trên đường chéo phụ.

Dữ liệu vào:

• Dòng đầu chứa số n.
• Dòng thứ i trong n dòng tiếp theo chứa n số nguyên lần lượt ứng với các phần tử nằm trên dòng thứ i của bảng A.

Dữ liệu ra:

• Ghi một số nguyên duy nhất là kết quả bài toán trên.

Ví dụ:

Input

4
1 2 3 4
4 3 2 0
0 2 3 4
1 4 5 6

Output

9

Ma trận chuyển vị của ma trận A có n hàng và m cột là ma trận ~A^T~ có m hàng và n cột, trong đó các phần tử ở hàng của ma trận A sẽ thành cột của của ma trận ~A^T~

Yêu cầu: In ra ma trận chuyển vị của ma trận A

Dữ liệu vào:

• Dòng 1. Ghi 2 số nguyên n,m tương ứng là số hàng số côt của ma trận (~1 \le n,m \le 1000~)
• n dòng tiếp theo mỗi dòng ghi m số nguyên. (~|a[i][j]|\le 10^4~)

Dữ liệu ra:

• In ra ma trận chuyển vị của ma trận đã cho

  Ví dụ:

  Input

3 4
1 2 3 4
5 6 7 8
9 10 11 12

Output

1 5 9
2 6 10
3 7 11
4 8 12

Cho một hình vuông A gồm n×n ô vuông, trên mỗi ô vuông chứa 1 số nguyên(n≤1000), các dòng được đánh số trên xuống dưới bắt đầu từ 1, các cột được đánh số từ trái qua phải cũng bắt đầu từ 1. Mỗi số trong bảng có giá trị tuyệt đối không vượt quá 10000. Đường chéo chính của bảng là đường thẳng nối hai ô (1,1) và(n,n). Một bảng được gọi là đối xứng nếu lấy các phần tử trên đường chéo chính làm trục đối xứng, các phần tử nằm về 2 phía của trục đối xứng tương ứng bằng nhau.

Yêu cầu: Hãy kiểm tra xem một bảng hình vuông cho trước có đối xứng hay không.

Dữ liệu vào:

• Dòng đầu chứa số n.
• Dòng thứ i trong n dòng tiếp theo chứa n số nguyên lần lượt ứng với các phần tử nằm trên dòng thứ i của bảng A.

Dữ liệu ra:

• Nếu bảng trên đối xứng thì ghi 1, ngược lại ghi 0.

Ví dụ

Input

5
1 2 3 1 9
2 2 6 7 6
3 6 3 8 12
1 7 8 1 3
9 6 12 3 4

Output

1

Trên đây là một ví dụ về hình vuông đối xứng

Cho một hình vuông A gồm n×n ô vuông, trên mỗi ô vuông chứa 1 số nguyên(n≤1000), các dòng được đánh số trên xuống dưới bắt đầu từ 1, các cột được đánh số từ trái qua phải cũng bắt đầu từ 1. Mỗi số trong bảng có giá trị tuyệt đối không vượt quá 10000. Đường chéo chính của hình vuông là đường thẳng nối hai ô (1,1) và(n,n). Các ô nằm phía dưới đường chéo chính (bao gồm cả các ô thuộc đường chéo chính) được gọi là tam giác dưới của hình vuông.

Yêu cầu: Tính tổng các ô thuộc tam giác dưới của hình vuông.

Dữ liệu vào:

• Dòng đầu chứa số n.
• Dòng thứ i trong n dòng tiếp theo chứa n số nguyên lần lượt ứng với các phần tử nằm trên dòng thứ i của bảng A.

Kết quả:

• Ghi một số nguyên duy nhất là tổng các phần tử thuộc tam giác dưới của hình vuông.

Tam giác dưới màu vàng

Ví dụ:

Input

4
1 2 3 4
4 3 2 0
0 2 3 4
1 4 5 6

Output

29

Cho một hình vuông A gồm n×n ô vuông, trên mỗi ô vuông chứa 1 số nguyên(n≤1000), các dòng được đánh số trên xuống dưới bắt đầu từ 1, các cột được đánh số từ trái qua phải cũng bắt đầu từ 1. Mỗi số trong bảng có giá trị tuyệt đối không vượt quá 10000. Đường chéo chính của hình vuông là đường thẳng nối hai ô (1,1) và(n,n). Các ô nằm phía trên đường chéo chính (bao gồm cả các ô thuộc đường chéo chính) được gọi là tam giác trên của hình vuông.

Yêu cầu: Tính tổng các ô thuộc tam giác trên của hình vuông.

Dữ liệu vào:

• Dòng đầu chứa số n.
• Dòng thứ i trong n dòng tiếp theo chứa n số nguyên lần lượt ứng với các phần tử nằm trên dòng thứ i của bảng A.

Kết quả:

• Ghi một số nguyên duy nhất là tổng các phần tử thuộc tam giác trên của hình vuông.

Tam giác trên màu vàng

Ví dụ:

Input

4
1 2 3 4
4 3 2 0
0 2 3 4
1 4 5 6

Output

28

Cho một bảng gồm N hàng, M cột. Các hàng của bảng được đánh số từ 1 đến N từ trên xuống dưới, các cột của bảng được đánh số từ 1 đến M từ trái qua phải. Ô nằm trên giao của hàng i và cột j được gọi là ô (i, j) và trên đó chứa một số nguyên dương là A[i, j] (~1 ≤ i, j ≤ N~)

Yêu cầu: Ứng với mỗi bộ (~h1,c1~) và (~h2,c2~) cho trước hãy tính và in ra tổng tất cả các ô nằm trên hình chữ nhật được tạo bởi giao giữa hàng ~h1~, cột ~c1~; hàng ~h2~, cột ~c2~.

Dữ liệu vào:

Cho trong file tonghcn.inp có cấu trúc như sau:

• Dòng 1: Ghi hai số nguyên dương ~N~, ~M~ (~1 ≤ N ≤ M ≤ 10^3~ ).
• Dòng thứ i trong N dòng tiếp theo: Ghi ~M~ số nguyên dương, số thứ j là ~A[i, j]~ (~A[i, j] ≤ 10^3~).
• Dòng thứ N+2: Ghi số nguyên dương T là số lượng bộ test cần tìm (~T ≤ 10^3~.
• T dòng tiếp theo mỗi dòng ghi 4 số nguyên dương ~h_1, h_2, c_1, c_2~.

Dữ liệu ra:

Ghi ra file tonghcn.out với cấu trúc như sau:

• Gồm T dòng, mỗi dòng ghi tổng tìm được ứng với T test đã cho.

Ví dụ:

Input

3 4
1 2 3 4
3 2 1 2
2 3 1 3
2
1 3 2 4
1 2 3 4

Output

21
10

Cho một bảng số gồm 𝑀 dòng và 𝑁 cột, các dòng được đánh số từ 1 đến ~𝑀~, các cột được đánh chỉ số từ 1 đến ~𝑁~, ô ở dòng 𝑖 cột 𝑗 có giá trị bằng ~𝑖^2 + 𝑗^2~. Các số trong bảng được sắp xếp tăng dần tạo thành dãy ~𝐴~ có các phần tử được đánh chỉ số từ 1 đến ~𝑀 × 𝑁~.

Yêu cầu: Cho biết 𝑇 số nguyên ~𝑥_1, 𝑥_2, … , 𝑥_𝑇~, hãy tìm giá trị thứ ~𝑥_𝑖~ của dãy ~𝐴~.

Dữ liệu vào:

• Dòng đầu ghi ba số nguyên dương ~𝑀~, ~𝑁~, ~𝑇~ (~1 ≤ 𝑇 ≤ 10~);

• Dòng thứ hai ghi ~𝑇~ số lần lượt ~𝑥_1, 𝑥_2, … , 𝑥_𝑇~ (~1 ≤ 𝑥_𝑖 ≤ 𝑀 × 𝑁~); Các số trong tệp ghi cách nhau ít nhất một dấu cách.

Kết quả:

• Gồm ~𝑇~ dòng, mỗi dòng ghi một giá trị tương ứng tìm được.

Ràng buộc:

• Có 50% số điểm ~1 ≤ 𝑀~, ~𝑁 ≤ 500~;

• Có 30% số điểm ~1 ≤ 𝑀 × 𝑁 ≤ 1000000~;

• Có 20% số điểm ~10000 < 𝑀, 𝑁 ≤ 100000~.

Ví dụ:

Input

3   4   2
3   8   

Output

5
13

Giải thích: