UOJ Logo

NOI.AC

1S 512MB

#2907. moon

统计

题目描述

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所有坐标1061n,q1000