Cho một bảng kích thước ~n \times m~ ô, 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 ~x~ và cột ~y~ là ô ~(x, y)~. Mỗi ô của bảng được sơn một trong 2 màu trắng hoặc đen, nếu ~x+y~ là số chẵn – ô có màu trắng, trong trường hợp ngược lại – ô có màu đen.

Bạn Yumi dùng các hộp sơn sơn đảo màu một số ô, tức là ô trắng thành ô đen và ngược lại. Yumi thực hiện ~q~ lần, mỗi lần Yumi đổi màu 1 ô, bạn Moon lại nhìn và tính toán phải sơn đổi màu ít nhất bao nhiêu ô để tạo thành bảng gồm 2 phần sao cho, tồn tại một ~t~ để các ô ở các dòng trên ~t~ có màu đen, các ô còn lại (từ dòng ~t~ trở xuống) – có màu trắng, một số trường hợp, sau khi sơn đổi màu, bảng có thể chỉ có một màu. Moon vốn có trí nhớ rất tốt nên đã nhớ dãy các số mà mình tính được.

Moon đố bạn hãy tìm ra dãy số ấy.

Yêu cầu: Tìm dãy số mà Moon đã tính được sau mỗi lần đổi màu.

Input

• Dòng đầu tiên chứa 2 số nguyên ~n~ và ~m~ (~1 \le n \le 2 \times 10^5~, ~1 \le m \le 10~).
• Dòng thứ 2 chứa số nguyên ~q~ (~1 \le q \le 2 \times 10^5~).
• Mỗi dòng trong ~q~ dòng tiếp theo chứa 2 số nguyên ~x~ và ~y~ (~1 \le x \le n, 1 \le y \le m~).

Output

• Các số mà Moon đã 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