题目描述

在月球上工作的辉夜姬听到彩叶的歌声，决定再去一趟地球。

月球和地球之间有一块陨石，如果撞上这块陨石，就会回到 8000 年以前，辉夜姬想要回到彩叶唱歌的夜晚，于是她决定避开这块陨石，并且在有限时间内来到地球。

形式化题面：

在二维平面上，有一个凸多边形 \(C\)，其顶点数为 \(N\)。多边形 \(C\) 的顶点按逆时针顺序为 \(\left( x_1, y_1\right), \left(x_2, y_2\right), \dots, \left(x_N, y_N\right)\)。

有 \(Q\) 次询问，每次询问给出两个点 \(S = \left(s_x, s_y\right)\) 和 \(T = \left(t_x, t_y\right)\)，和一个浮点数 \(d\),（保证点 \(S\) 和 \(T\) 均严格在多边形外部，且不在多边形边界）。判断以点 \(S\) 为起点，点 \(T\) 为终点，是否存在一条长度不超过 \(d\) 的路径，要求路径不得进入多边形 \(C\) 的内部（但允许经过其边界）。

输入格式

第一行输入一个整数 \(T\) 表示测试数据组数。

对于每组数据：

第一行输入两个整数 \(N, Q\) 表示凸多边形的顶点数量和询问次数。

接下来 \(N\) 行，每行输入两个浮点数 \(x_i, y_i\)，凸多边形上表示第 \(i\) 个点的坐标。

接下来 \(Q\) 行，每行输入四个浮点数 \(s_x, s_y, t_x, t_y\) 和一个浮点数 \(d\)，表示一组询问 \(S = \left(s_x, s_y\right)\) 和 \(T = \left(t_x, t_y\right)\)。

数据保证给出一个合法的凸多边形，不存在三点共线，询问给出的点均严格在多边形外部，且不在多边形边界。

如果从 \(S\) 到 \(T\) 的理论最短路径长度为 \(d_{min}\)，保证给出的 \(d\) 满足 \(|d-d_{min}| \ge 10^{-4}\)。

令 \(N_{tot}\) 表示所有测试组 \(N\) 之和， \(Q_{tot}\) 表示所有测试组 \(Q\) 之和。

\(1 \le T \le 100, 1 \le N_{tot}, Q_{tot} \le 2 \times 10^5\)。

对于每组数据：

\(|x_i|, |y_i|, |s_x|, |s_y|, |t_x|, |t_y| \le 10^5, d \le 10^6\)。

\(3 \le N\)。

输入中所有浮点数小数点后的位数不会超过 \(7\)。

输出格式

对于每组数据：

输出 \(Q\) 行，对于每组询问，如果存在符合要求的路径，输出单行字符串 "Yes"，否则输出单行字符串 "No"。

输出区分大小写

样例输入

2
5 5
5 0
1 4
-4 2
-4 -2
1 -4
7 -5 10 -7 3.6
-7 9 -2 10 5.1
6 -6 5 -9 3.2
-9 -2 1 -4 10.2
-10 8 6 -3 20
8 8
1.815869 5.843392
-6.402481 3.597517
-6.319297 -3.679320
-6.151667 -3.835793
-2.258571 -5.755919
-0.068164 -5.999782
1.243600 -5.927063
6.844729 -3.105914
-7.696176 4.544950 -3.255233 -9.303071 14.753040
3.983767 9.020432 -9.072549 -1.868772 17.810307
-2.369852 6.386474 -8.059800 -5.163218 13.818208
-0.165644 -6.672256 -5.693888 -6.119447 5.545805
6.851962 -9.182809 5.063777 9.871202 19.175962
9.653594 3.164725 -4.106512 5.460949 14.227531
2.161436 9.984498 9.811317 -4.208692 16.121492
-4.227538 -7.987818 -1.651629 9.434430 19.591694

样例输出

No
Yes
Yes
Yes
No
Yes
Yes
No
No
Yes
Yes
No
No