题目描述

平面上有 $n$ 个点，点 $i$ 的坐标为 $(x_i,y_i)$，颜色为 $c_i$。每个点以恒定速度沿向量 $(dx_i,dy_i)$ 运动。也就是说，每经过一秒，点 $i$ 的横坐标增加 $dx_i$，纵坐标增加 $dy_i$。

对于前 $T$ 秒中的所有整数时刻，求不同颜色点之间最大距离的最小值。

换句话说，需要找到一个整数时刻 $t$（$0\le t\le T$），使得在该时刻，不同颜色点对之间的最大距离相比其他所有整数时刻最小。

输入格式

每个测试包含多组数据。

第一行包含一个整数 $t$（$1\le t\le 100000$），表示数据组数。

接下来依次给出每组数据。

每组数据第一行包含两个整数 $n,T$（$2\le n\le 200000$，$0\le T\le 10^8$），分别表示点的数量和考虑的时间区间。

接下来 $n$ 行描述点。第 $i$ 行包含五个整数 $x_i,y_i,dx_i,dy_i,c_i$（$-10^8\le x_i,y_i,dx_i,dy_i\le 10^8$，$1\le c_i\le n$），分别表示点的坐标、两个坐标方向的速度以及点的颜色。

保证至少存在两个颜色不同的点。

保证每个测试中所有数据组的 $n$ 之和不超过 $200000$，所有数据组的 $T$ 之和不超过 $10^8$。

保证任意点在 $0$ 到 $T$ 的任意时刻，其坐标绝对值不超过 $10^9$。

输出格式

对于每组数据，输出一行一个数，表示前 $T$ 秒中不同颜色点之间最大距离的最小值。

若答案的绝对误差或相对误差不超过 $10^{-9}$，则认为正确。

形式化地，设你的答案为 $a$，标准答案为 $b$，当且仅当

时答案会被接受。

样例

3
3 0
1 1 0 0 1
2 2 0 0 2
4 4 0 0 1
2 2
0 0 1 1 1
2 2 -1 -1 2
4 100
0 0 0 1 1
4 0 -1 0 2
4 4 0 -1 1
0 4 1 0 2

2.82842712474619009753
0.00000000000000000000
2.82842712474619009753

样例解释

第一组数据中，只考虑一个时刻。第一点与第二点距离为 $\sqrt{2}$，第二点与第三点距离为 $2\sqrt{2}$，因此答案为 $2\sqrt{2}$。

第二组数据中，在时刻 $1$，两个点重合，因此不同颜色点之间距离最大值为 $0$，答案为 $0$。

第三组数据中，可以证明不同颜色点之间最大距离的最小值在时刻 $2$ 取得，值为 $2\sqrt{2}$。

第三组数据在 $t=0,1,2$ 三个时刻的状态，其中颜色 $1$ 的点用红色标记，颜色 $2$ 的点用蓝色标记：

评分方式

本题测试点由 9 个分组组成。只有通过某一组及其要求的部分前置分组时，才能获得该组分数。注意，部分分组不要求通过样例。Offline-testing 表示该组测试结果只会在比赛结束后给出。

设 $\sum n$ 为当前测试中所有数据组的 $n$ 之和，$\sum T$ 为所有数据组的 $T$ 之和。