1995. Yukari

【题目背景】

幻想乡的创始人之一，八云紫，有着强大的控制结界的能力，可以瞬间消除一定范围内所有弹幕。我们可以将其消除范围视为一个矩形，而弹幕可以视为动点。

八云紫想要嘲讽她的敌人，所以她希望只使用一次消除能力，尽可能多地消除弹幕。

请你告诉她，在哪一时刻使用道具，可以消除尽可能多的弹幕。

【问题描述】

在平面上给定一个矩形区域(也可能退化成线段或者点)。

矩形的边与坐标轴平行，左下端点为 $(x_l,y_l)$，右上端点为 $(x_r,y_r)$。

给定 $n$ 个动点，初始坐标为 $(x_i, y_i)$，运动方向为 $(u_i,v_i)$，速度为 $\sqrt{(u_i)^2+(v_i)^2}$

求在哪一时刻 $t (t ∈ N)$，在矩形内部及边界的动点数目最多。

如果有多个 $t$ 满足条件，输出最小的 $t$ 即可。

【输入格式】

第一行 5 个正整数，$n, x_l, y_l, x_r, y_r$，表示动点个数和矩形区域。

接下来 $n$ 行，每行 4 个整数，$x_i, y_i, u_i, v_i$ ，描述第 $i$ 个动点。

【输出格式】

在矩形内部及边界的动点数目最多的时刻 $t (t ∈ N)$。

如果有多个 $t$ 满足条件，输出最小的 $t$ 即可。

【输入样例1】

2 2 2 3 3
3 1 -1 1
2 3 1 -1

【输出样例1】

1

【输入样例2】

13 44 68 49 73
40 46 2 6
28 75 4 -1
32 61 3 3
41 64 2 1
40 99 2 -7
54 49 -2 6
32 80 4 -2
73 99 -7 -7
23 93 6 -5
44 96 0 -6
36 70 3 0
70 98 -6 -7
75 53 -7 4

【输出样例2】

4

【数据范围】

对于前 40% 数据，$1\leq n \leq 100, 1 \leq x_l, x_r, y_l, y_r, x_i, y_i \leq 100, -10 \leq u_i, v_i \leq 10$；

对于100% 数据,$1\leq n \leq 10^5, 1 \leq x_l, x_r, y_l, y_r, x_i, y_i \leq 10^9, 0 \leq |u_i|, |v_i|\leq 10^5, x_l \leq x_r, y_l \leq y_r$。

保证 $n，x_l，x_r，y_l，y_r，x_i，y_i，u_i，v_i$ 均为整数.