平面上有 n 道以原点为圆心的圆形墙,半径依次为 r1<⋯<rn。第 i 道墙上有 ki 扇门。
令 M=360000000。角度参数为 p 的门位于
$$\left(r_i\cos\frac{2\pi p}{M},\ r_i\sin\frac{2\pi p}{M}\right).$$
墙的厚度和门的宽度均视为 0。可以在平面上行走,也可以沿墙行走,但只有经过门才能穿过墙,不能直接穿墙或越过墙。
有 m 次独立询问。询问 (t,q) 的起点位于第 t 道墙的内侧并无限接近墙面,其角度参数为 q。求从该位置到原点的最短路长度;不能到达时回答 −1。
输入格式
第一行是 n,m,2≤n≤2×105,1≤m≤2×105。
随后 n 行,第 i 行依次给出 ri,ki,pi,1,…,pi,ki。
- 1≤r1<⋯<rn≤108;
- 0≤ki≤2×105,∑ki≤2×105,kn=0;
- 门的角度满足 0≤pi,1<⋯<pi,ki<M。
最后 m 行各给出 t,q,其中 1≤t≤n,0≤q<M。
输出格式
按询问顺序输出 m 行。不可达时输出 -1,否则输出最短距离。绝对误差或相对误差不超过 10−6 即可。
样例 1
输入
3 4
2 2 0 90000000
5 0
8 0
1 114514
2 0
2 180000000
3 233
输出
2.0000000000
5.0000000000
7.4056093871
-1