Cho bàn cờ kích thước ~m×n~ chứa các số nguyên và ~q~ quân mã rải rác trên bàn cờ. Các dòng trên bàn cờ được đánh số từ 1 đến ~m~, các cột từ 1 đến ~n~.

Hỏi mỗi quân mã có thể di chuyển đến những ô nào trong bàn cờ, trong một nước, hãy trả ra tổng giá trị của các ô đó.

Dữ liệu

• Dòng đầu chứa 3 số nguyên ~m, n, q~. ~(m, n, q \le 100)~
• ~m~ dòng tiếp theo, mỗi dòng chứa ~n~ phần tử là giá trị của bảng. Các giá trị không quá ~10^4~
• ~q~ dòng cuối cùng, mỗi dòng chứa cặp chỉ số của quân mã thứ ~i~ (~1 \le i \le q~).

Kết quả

Gồm ~q~ dòng, tương ứng câu trả lời cho từng quân mã.

Input

3 4 2
6 9 6 3 
6 7 10 3 
4 4 10 7 
2 2
3 1

Output

10
19