Trên trục tọa độ ~Oxy~, cho tọa độ điểm ~I~. Có ~n~ đoạn thẳng và một số nguyên ~k~, đoạn thứ ~i~ có hai đầu mút là ~2~ điểm ~A_i~ và ~B_i~. Đường tròn có tâm ~I~ và bán kính ~R~ với ~R~ là số nguyên không âm, gọi tắt là ~(I,R)~, được gọi là tốt nếu chỉ có bé hơn hoặc bằng ~k~ đoạn thẳng có điểm nằm bên trong hoặc bên trên đường tròn.

Hãy tìm số nguyên không âm ~R~ lớn nhất sao cho đường tròn ~(I,R)~ là tốt.

Input

• Dòng đầu gồm hai số nguyên ~x_I,y_I~ miêu tả tọa độ của điểm ~I~.
• Dòng thứ hai gồm ~2~ số nguyên dương ~n~ và ~k~.
• ~n~ dòng sau, mỗi dòng gồm hai cặp số nguyên: ~x_{A_i},y_{A_i}~ và ~x_{B_i},y_{B_i}~ là hai đầu mút của đoạn thẳng thứ ~i~.

Output

• In ra ~R~ là kết quả của bài toán.

Constraints .

• ~1 \le k < n \le 10^5~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^6,10^6]~.

Subtask

• Sub ~1~ (~50\%~): ~n \le 1000~ và tọa độ của các điểm đều nằm trong khoảng ~[-10^3,10^3]~.
• Sub ~2~ (~50\%~): Không giới hạn gì thêm.

Sample Input 1

0 0
4 2
-4 4 1 5
-3 2 -1 1
2 2 6 4
-3 -2 -1 -4

Sample Output 1

3

Explanation 1

Đường tròn tâm ~A~ với bán kính là ~3~ gồm ~2~ đoạn thẳng có điểm nằm bên trong hoặc bên trên đường tròn là ~DE~ và ~FG~, đây là bán kính lớn nhất thỏa mãn.