题目描述
nz 国的王子在天空中走丢了,公主急于去找她。天空是一个二维平面,有 n 个月亮,第 i 个月亮的坐标是 (xi,yi)。
月亮可以抽象为圆。第 0 秒时,月亮的半径都是 1。每过一秒,每个月亮的半径都会增长 1。注意只有在时间是整数时月亮的半径才会变化。
公主的坐标为 (px,py),她通过心灵感应得到了王子的坐标 (qx,qy)。每秒她都可以向上下左右四个方向中选一个移动一格。
现在已经是第 0 秒了,她不希望碰到月亮(在圆内或在圆上,包括出发和结束的瞬间都不能碰到),又不想太早动身。请你帮她计算最晚在哪个整数秒出发能不碰到月亮找到王子,或者告诉她没有方案。
一共有 q 组相互独立的询问。
输入格式
第一行两个整数 n,q。
接下来 n 行,每行两个整数 xi,yi。
接下来 q 行,每行四个整数 px,py,qx,qy。
输出格式
输出 q 行,每行一个整数表示答案,无解输出 -1。
样例输入
3 3
1 7
1 2
8 5
0 0 1 1
11 2 11 1
6 5 4 5
样例输出
-1
2
0
数据范围
所有坐标均为整数,保证王子与公主的坐标不同。
对于 50% 的数据,所有横坐标均为 0。
对于 100% 的数据,0≤所有坐标≤106,1≤n,q≤1000。