Cuộc thi Robot tự hành năm nay có chủ đề về việc tiết kiệm năng lượng. Sân thi đấu cho các robot được thiết kế dưới dạng hình chữ nhật kích thước ~W\times L~ và được chia thành các ô vuông đơn vị, xếp thành ~W~ dòng và ~L~ cột. Ô có toạ độ ~(r,c)~ là ô nằm tại dòng thứ ~r~ từ trên xuống (~1\le r\le W~) và tại cột thứ ~c~ từ trái sang (~1\le c\le L~). Ban đầu, sân thi đấu có ~N~ trạm sạc điện cho robot, mỗi trạm đặt tại một ô khác nhau. Với mỗi lượt thi đấu, robot sẽ được đặt vào một ô bất kì, tính cả các ô đã có trạm sạc điện. Sau khi được đặt vào sân, robot sẽ phải tìm đường đi có ít bước di chuyển nhất có thể tới một trạm sạc điện. Một bước di chuyển của robot là việc di chuyển từ ô hiện tại tới một trong các ô kề cạnh nằm trong sân thi đấu, đồng thời mất đúng một đơn vị năng lượng.

Trong quá trình thi đấu, giám khảo sẽ liên tục đưa thêm vào hoặc bỏ bớt đi các trạm sạc điện trong sân. Sau mỗi lần thay đổi, đội chơi sẽ phải nạp lại mức năng lượng tối thiểu cho robot của mình để đặt lại vào một ô bất kì của sân thi đấu nhằm đảm bảo robot đến được một trạm sạc điện trước khi hết năng lượng.

Tuấn là đội trưởng đội Robot tự hành đại diện cho tỉnh mình tham gia vòng một cấp Quốc gia. Để chuẩn bị cho cuộc thi, đội Tuấn phải thiết kế và lập trình thuật toán cho robot theo luật thi đấu của ban tổ chức đề ra.

Yêu cầu: Hãy giúp Tuấn tính năng lượng tối thiểu cho robot đặt vào sân thi đấu ban đầu và năng lượng tối thiểu cho robot sau mỗi lần ban tổ chức thay đổi trạm sạc điện trong sân.

Dữ liệu

Vào từ file văn bản ROBOT.INP:

• Dòng đầu chứa bốn số nguyên dương ~W,L,N,Q~ là kích thước của sân chơi ~W\times L~, số trạm sạc điện ban đầu và số lượng truy vấn ~(W\le 15; L \le 10^9; N \le 50000; Q\le 10^5)~.

• Mỗi dòng trong số ~N~ dòng tiếp theo chứa hai số nguyên dương ~r~ và ~c~ là toạ độ của một trạm sạc điện ~(1 \le r \le W; 1 \le c \le L)~. Dữ liệu đảm bảo không có hai trạm sạc điện nào trùng toạ độ ô đặt.

• Mỗi dòng trong số ~Q~ dòng tiếp theo tương ứng với ~Q~ truy vấn thay đổi chứa hai số nguyên dương ~r~ và ~c~ ~(1 \le r \le W; 1 \le c \le L)~. Nếu ô ~(r,c)~ đang có trạm sạc điện thì ban tổ chức sẽ loại bỏ trạm đó. Trái lại, ban tổ chức sẽ bổ sung thêm vào một trạm sạc điện tại ô ~(r,c)~.

Dữ liệu đảm bảo sau mỗi truy vấn luôn có ít nhất một trạm sạc điện trên sân.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra file văn bản ROBOT.OUT gồm ~Q+1~ dòng:

• Dòng đầu tiên ghi một số nguyên là năng lượng tối thiểu tìm được cho robot đặt vào sân thi đấu ban đầu.

• Dòng thứ ~i~ trong ~Q~ dòng tiếp theo ghi một số nguyên là năng lượng tối thiểu tìm được sau truy vấn thay đổi thứ ~i~.

Ràng buộc

• Có ~16\%~ số test ứng với ~16\%~ số điểm thoả mãn: ~W=1~.

• ~20\%~ số test khác ứng với ~20\%~ số điểm thoả mãn: ~W=3~.

• ~14\%~ số test khác ứng với ~14\%~ số điểm thoả mãn: ~Q,L,N\le 200~.

• ~20\%~ số test khác ứng với ~20\%~ số điểm thoả mãn: ~Q=1~.

• ~14\%~ số test khác ứng với ~14\%~ số điểm thoả mãn: ~L\le 10000~; ~Q\le 100~.

• ~16\%~ số test khác ứng với ~16\%~ số điểm không có ràng buộc gì thêm.

Ví dụ

Input

3 7 1 2
2 3
3 7
2 3

Output

5
3
8

Giải thích

Trong ví dụ trên:

• Ban đầu, năng lượng cần tìm tối thiểu là ~5~, chẳng hạn khi đặt robot vào ô ~(3, 7)~.

• Sau khi thêm trạm sạc điện ở ô ~(3, 7)~ thì năng lượng tối thiểu cần tìm là ~3~, chẳng hạn khi robot đặt vào ô ~(1, 5)~.

• Ở lần thay đổi thứ hai, do ô ~(2, 3)~ có trạm sạc điện nên trạm đó sẽ bị loại bỏ. Khi đó, năng lượng tối thiểu cần tìm là ~8~, đó là trường hợp robot đặt vào ô ~(1, 1)~.