Một hôm Chưng và Quýt được giao nhiệm vụ dọn dẹp tấm bảng sau nhà. Tấm bản là một bàn cờ kích thước nxm ô, các hàng được đánh số từ trên xuống dưới từ 1 đến n, các cột đánh số từ 1 đến m từ trái qua phải. Giao giữa hàng ~a~ và cột ~b~ là ô ~(a, b)~. Mỗi ô của bàn cờ được sơn một trong 2 màu trắng hoặc đen, nếu ~a+b~ là số chẵn – ô có màu trắng, trong trường hợp ngược lại – màu đen. Tai hoạ là gần đây Chưng đã học thêm được cho mình một kỹ năng vẽ ux, ui design mới nên bỗng nhiên cậu nổi máu nghệ sĩ, muốn dùng các hộp sơn phun cạnh đó tạo một bức tranh trừu tượng bằng cách sơn đảo màu một số ô, tức là ô trắng thành ô đen và ngược lại.

Quýt là một người vốn say mê tin học và thiết kế nên không thể khoanh tay đứng nhìn bạn vẽ như vậy. Quýt nghĩ thầm, thà sơn sao cho tồn tại một t để các ô ở các dòng từ t trở lên có màu đen, các ô còn lại (từ dòng t+1 trở xuống) – có màu trắng. Ít ra như vậy cũng còn dùng như tấm bảng vừa có thể viết phấn (ở phần màu đen) và viết bút dạ (ở phần màu trắng). Lứu ý trong trường hợp bảng toàn màu đen vẫn chấp nhận.

Cứ mỗi lần sơn lại một ô, Chưng lại đứng ngắm nhìn và suy nghĩ chọn ô tiếp theo, còn Quýt thì nhẩm tính bây giờ phải sơn đổi màu ít nhất bao nhiêu ô để tạo thành bảng 2 phần như mình muốn. Vốn có trí nhớ tốt, Quýt nhớ hết các số đó. Sau khi Chưng sơn lại ô thứ q thì sự kiên nhẫn của Quýt cũng cạn kiệt, cô dứt khoát yêu cầu Chưng khiêng bảng đi cất. Khi ra về, những số đã nhớ trong dãy tính được vẫn hiện rõ trong đầu của Quýt Vì vậy bạn hãy cùng Chưng thử đoán xem những số đó là những số nào?

Input

• Dòng đầu tiên chứa 2 số nguyên ~n~ và ~m~ ~(1 ≤ n ≤ 2×10^5, 1 ≤ m ≤ 10)~,

• Dòng thứ hai chứa số nguyên ~q~ ~(1 ≤ q ≤ 2×10^5)~,

• Mỗi dòng trong q dòng tiếp theo chứa 2 số nguyên ~a~ và ~b~ ~(1 ≤ a ≤ n, 1 ≤ b ≤ m).~

Output

• Các số đã nhẩm tính được theo trình tự tính, mỗi số trên một dòng.

Sample Input 1

5 4
4
1 1
5 1
1 3
2 3

Sample Output 1

9
8
7
8