#P13099. Xor Circle

Xor Circle

Background

CCPC(中国大学生程序设计竞赛)将在 A 城举办。A 城可以被视为一个无限二维平面。有 nn 名选手将参加比赛,这些人编号为 11 到 nn,每个人在 A 城中有一个初始位置和一个数值 aia_i。

主办方需要选择一个比赛举办地点。对于每个人 ii,当且仅当比赛地点与他/她的初始位置的距离不超过 dd 时,他/她才会感到满意。注意,比赛地点的坐标可以是任意实数。

为了判断一个地点是否是好地点,主办方定义函数 f(P)f(P):如果将 PP 作为比赛地点,则 f(P)f(P) 是所有满意人的数值的某个子集的最大异或和。

设 S(P)S(P) 表示所有与 PP 的距离不超过 dd 的人,g(T)g(T) 表示集合 TT 中所有 aia_i 的异或值(特别地,g(∅)=0g(\emptyset) = 0),则 f(P)=max⁡T⊆S(P)g(T)f(P) = \max_{T \subseteq S(P)} g(T)。当且仅当 f(P)≥kf(P) \geq k 时,点 PP 被认为是好地点。

你的任务是找出一个最小的非负实数 dd,使得存在至少一个好地点。

注意两点之间的距离公式为:
dist=(xA−xB)2+(yA−yB)2\text{dist} = \sqrt{(x_A - x_B)^2 + (y_A - y_B)^2}。

Format

Input

第一行输入两个整数 n(1≤n≤1000),k(0≤k<220)n(1 \leq n \leq 1000), k(0 \leq k < 2^{20}),表示选手人数和好地点的最小值。

接下来 nn 行,每行输入三个整数 xi,yi,aix_i, y_i, a_i,其中 ∣xi∣,∣yi∣≤104|x_i|, |y_i| \leq 10^4,0≤ai<2200 \leq a_i < 2^{20},表示第 ii 个选手的位置和对应的数值。

Output

输出一个非负实数 dd,表示使得至少存在一个好地点的最小距离。

当且仅当你的答案与标准答案的绝对误差或相对误差不超过 10−610^{-6} 时,将被认为是正确的。

如果不存在这样的 dd,请输出 -1。

Samples

4 39
-1 -1 5
2 3 37
-1 2 2
-1 -1 14
1.5811388301
4 16
1 1 4
5 1 4
1 9 1
9 8 10
-1
2 0
11 45 14
191 98 10
0.0000000000
序号 限制 分值
1 n≤10n \leq 10 15
2 n≤100n \leq 100,且所有 xi,yi∈[−1000,1000]x_i, y_i \in [-1000, 1000]
3 n≤100n \leq 100,值域 ai<220a_i < 2^{20}
4 n≤1000n \leq 1000, xi,yi≤103x_i, y_i \leq 10^3
5 n≤1000n \leq 1000,xi,yi∈[−104,104]x_i, y_i \in [-10^4, 10^4],0≤ai<2200 \leq a_i < 2^{20} 40