Truy vấn

Cho một bảng kích thước $N\times M$ gồm $N$ hàng và $M$ cột. Các hàng được đánh số từ $1$ đến $N$ từ trên xuống dưới, các cột được đánh số từ $1$ đến $M$ từ trái sang phải. 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 ,\lceil \frac{N·M}{2}\rceil$ vào các ô cách nhau một ô theo thứ tự duyệt trên, bắt đầu từ ô đầu tiên (tức là vào ô thứ $1,3,5,\dots$ theo thứ tự duyệt). Sau đó, tiếp tục điền các số còn lại $\lceil \frac{N·M}{2}\rceil +1,\dots ,N·M$ vào những ô còn trống, cũng theo đúng thứ tự duyệt trên.

Ví dụ với $N=3$, $M=4$, bảng sau khi điền là:

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$.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên $N,M$ ($1\le N,M\le {10}^9$).
• Dòng tiếp theo chứa số nguyên $Q$ ($1\le Q\le {10}^5$).
• $Q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $x,y$ ($1\le x\le N$, $1\le y\le M$) mô tả một truy vấn.

Dữ liệu ra

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 dấu cách.

Ràng buộc

• $1\le N,M\le {10}^9$.
• $1\le Q\le {10}^5$.
• $1\le x\le N$, $1\le y\le M$.
• $25\%$ số test có $N,M\le 100$.
• $25\%$ số test khác có $N,M\le {10}^5$.
• $50\%$ số test còn lại có $N,M\le {10}^9$.

Ví dụ