Cho một bảng kích thước ~N \times M~. Duyệt các ô theo thứ tự từ trái sang phải trên từng hàng và từ hàng trên xuống hàng dưới.

Ở lượt đầu tiên, điền lần lượt các số ~1, 2, \dots, \left\lceil \frac{N \cdot M}{2} \right\rceil~ vào các ô cách nhau một ô, bắt đầu từ ô đầu tiên. Sau đó, tiếp tục điền các số còn lại vào những ô trống theo đúng thứ tự duyệt trên.

Có ~Q~ truy vấn, mỗi truy vấn gồm hai số ~x, y~. Với mỗi truy vấn, hãy xác định số được ghi tại ô thuộc hàng ~x~, cột ~y~.

Input

• Dòng đầu tiên gồm hai số nguyên ~N, M~ ~(N, M \le 10^9)~;

• Dòng tiếp theo chứa số nguyên ~Q~ ~(Q \le 10^5)~;

• ~Q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~x, y~ mô tả một truy vấn.

Output

In ra ~Q~ số là câu trả lời cho các truy vấn theo thứ tự xuất hiện, các số cách nhau bởi một khoảng trắng.

Scoring

Sample Input 1

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

Sample Output 1

2 10 4 5 7