Alice đã chế tạo một robot thông minh và muốn thử nghiệm khả năng tìm đường của robot trên một lưới ô vuông kích thước ~m \times n~. Các hàng của lưới được đánh số từ ~1~ đến ~m~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải. Ô giao giữa hàng ~i~, cột ~j~ gọi là ô ~(i, j)~ và có ~d_{ij}~ viên kim cương. Sẽ có ~q~ lần thử nghiệm độc lập, lần thử nghiệm thứ ~t~ (~1 \le t \le q~) được mô tả bằng ô ~(x_t, y_t)~. Cụ thể, robot xuất phát tại ô ~(1, 1)~ tìm đường di chuyển đến ô ~(m, n)~, mỗi lượt robot chỉ được đi sang ô kề bên phải hoặc ô kề bên dưới và không đi vào ô ~(x_t, y_t)~, khi robot ở ô nào, robot sẽ thu thập hết kim cương tại ô đó, robot cần thu thập được nhiều kim cương nhất.

Yêu cầu: Với mỗi lần thử nghiệm, hãy giúp Alice tính số viên kim cương mà robot có thể thu thập được.

Input

• Dòng đầu tiên chứa ba số nguyên ~m, n, q~ (~2 < m \times n \le 3 \times 10^5; q \le m \times n - 2~);
• Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa ~n~ số nguyên không âm ~d_{i1}, d_{i2}, \dots, d_{in}~ (~d_{ij} \le 10^9~);
• Dòng thứ ~t~ trong ~q~ dòng tiếp theo chứa hai số nguyên dương ~x_t, y_t~ (~1 \le x_t \le m; 1 \le y_t \le n~). Chú ý, ô ~(x_t, y_t)~ khác ô ~(1, 1)~ và ô ~(m, n)~.

Output

• Gồm ~q~ dòng, dòng thứ ~t~ chứa một số nguyên tương ứng là số viên kim cương mà robot có thể thu thập được trong lần thử nghiệm thứ ~t~.