#P17901. Doo Doo Doo

Doo Doo Doo

平面上有 nn 道以原点为圆心的圆形墙,半径依次为 r1<⋯<rnr_1<\cdots<r_n。第 ii 道墙上有 kik_i 扇门。

令 M=360000000M=360000000。角度参数为 pp 的门位于

$$\left(r_i\cos\frac{2\pi p}{M},\ r_i\sin\frac{2\pi p}{M}\right).$$

墙的厚度和门的宽度均视为 00。可以在平面上行走,也可以沿墙行走,但只有经过门才能穿过墙,不能直接穿墙或越过墙。

有 mm 次独立询问。询问 (t,q)(t,q) 的起点位于第 tt 道墙的内侧并无限接近墙面,其角度参数为 qq。求从该位置到原点的最短路长度;不能到达时回答 −1-1。

输入格式

第一行是 n,mn,m,2≤n≤2×1052\le n\le2\times10^5,1≤m≤2×1051\le m\le2\times10^5。

随后 nn 行,第 ii 行依次给出 ri,ki,pi,1,…,pi,kir_i,k_i,p_{i,1},\ldots,p_{i,k_i}。

  • 1≤r1<⋯<rn≤1081\le r_1<\cdots<r_n\le10^8;
  • 0≤ki≤2×1050\le k_i\le2\times10^5,∑ki≤2×105\sum k_i\le2\times10^5,kn=0k_n=0;
  • 门的角度满足 0≤pi,1<⋯<pi,ki<M0\le p_{i,1}<\cdots<p_{i,k_i}<M。

最后 mm 行各给出 t,qt,q,其中 1≤t≤n1\le t\le n,0≤q<M0\le q<M。

输出格式

按询问顺序输出 mm 行。不可达时输出 -1,否则输出最短距离。绝对误差或相对误差不超过 10−610^{-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