1801. set2

给定 n 条直线 A_ix+B_iy+C_i=0 组成的集合 S,有 m 次询问,每次输入直线 l:Ax+By+C=0,并询问:

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

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

输入

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

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

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

输出

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

样例

标准输入 复制文本
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