Cho một bảng cỡ ~N \times M~ (các dòng đánh số từ ~1~ đến ~N~, các cột đánh số từ ~1~ đến ~M~) chứa các khối đèn cỡ ~1 \times 1~.

Khi bạn bật bóng đèn tọa độ ~(x; y)~ thì tất cả các bóng đèn ~(x'; y')~ thỏa mãn ~|x-x'|+|y-y'| \le K~ sẽ được bật sáng.

Có ~Q~ lần bật bóng đèn, sau mỗi lần bật bóng đèn, bạn hãy cho biết có bao nhiêu bóng đèn đang bật sáng.

Input

• Dòng ~1~ ghi ~4~ số nguyên ~N, M, K, Q~ ~(1 \le N, M, K \le 500; 1 \le Q \le 3 \cdot 10^5)~;

• ~Q~ dòng tiếp theo, dòng thứ ~i~ ~(1 \le i \le Q)~ ghi hai số nguyên dương ~x_i, y_i~ ~(1 \le x_i \le N, 1 \le y_i \le M)~ là tọa độ bóng đèn được bật ở lần thứ ~i~.

Output

Trên ~Q~ dòng, dòng thứ ~i~ là số bóng đèn sáng sau lần bật thứ ~i~

Scoring

Sample Input 1

7 8 2 5
2 2
4 3
1 8
5 6
2 2

Sample Output 1

11
20
26
37
37