Cho một ma trận số nguyên \(m \times n\).

Bạn phải trả lời \(q\) truy vấn, mỗi truy vấn trả lời tổng các phần tử cùng hàng và cùng cột với phần tử \((u,v)\)

Input

• Dòng đầu chứa hai số nguyên dương \(m\) và \(n\) \((m ,n \le 500)\)
• \(m\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên dương \((a_{i,j} \le 100000)\)
• Dòng tiếp theo chứa số nguyên dương \(q\) \((q \le 100)\) - số truy vấn.
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) - là tọa độ của phần tử cần trả lời.

Output

• Ứng với mỗi truy vấn, in ra đáp án cần tìm.

Example

3 3
4 6 7
1 3 4
2 4 6
2
1 3
2 2

27
18