1801. set2

给定 nn 条直线 Aix+Biy+Ci=0A_ix+B_iy+C_i=0 组成的集合 SS,有 mm 次询问,每次输入直线 l:Ax+By+C=0l:Ax+By+C=0,并询问:

  1. 找到 SS 满足斜率等于 ll 的直线 l:Ax+By+C=0l':A'x+B'y+C'=0,输出 CC';若不存在 ll',输出 no
  2. 找到 SS 满足斜率大于 ll 的直线里斜率最小的一条直线 l:Ax+By+C=0l':A'x+B'y+C'=0,输出 CC';若不存在 ll',输出 no
  3. 找到 SS 满足斜率小于 ll 的直线里斜率最大的一条直线 l:Ax+By+C=0l':A'x+B'y+C'=0,输出 CC';若不存在 ll',输出 no

特别地,若斜率不存在,我们认为斜率最大。

输入

输入一行两个整数 n,m(1n,m105)n,m(1\le n,m\le10^5)

接下来输入 nn 行,每行三个整数 Ai,Bi,Ci(109Ai,Bi,Ci109,Ai>0,Ai,BiA_i,B_i,C_i(-10^9\le A_i,B_i,C_i\le10^9,A_i > 0,A_i,B_i 不同时为零 )),代表第 ii 条直线。保证所有 nn 条直线斜率互异。

接下来输入 mm 行,每行三个整数 A,B,C(109A,B,C109,A>0,ABA,B,C(-10^9\le A,B,C\le10^9, A > 0,AB 不同时为零 )),代表一条询问的直线 ll

输出

对每条询问的直线 ll,在一行内以空格隔开输出上述的三个值。

样例

标准输入 复制文本
5 3
3 -3 1
2 -4 2
2 -1 3
1 0 4
0 1 5
1 -2 6
1 2 7
-5 0 8
标准输出 复制文本
2 1 5
no 5 no
4 no 3

提示

注:本题的强化版为 寄蒜几盒,可在本 OJ 找到,感兴趣可自行挑战。

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 32
通过 19