#P18126. Schoolgirls
Schoolgirls
Schoolgirls
Alice 学会了一种平行四边形工具:给定三个点 ,她可以构造点 ,使得有向向量 与 相等。三个输入点可以重合或共线。
称点 ()构成一个退化正多边形,当且仅当这些点全部重合。
称这些点按逆时针顺序构成一个非退化正多边形,当且仅当:
- 所有点互不相同;
- 它们位于同一个圆上;
- 对圆心 ,有
且每次逆时针旋转 都会把 变为 。
若存在这些点的一个排列能按逆时针顺序构成非退化正多边形,也称这些点构成非退化正多边形。
只要点集构成上述两种正多边形之一,就称它构成正多边形。该定义与点的排列顺序无关。
最开始有 个点,它们按逆时针顺序构成一个非退化正多边形。之后又用上述平行四边形工具构造了 个点。第 个点 使用此前三个点 构造,满足
$$\overrightarrow{K_{a_i}K_{b_i}} = \overrightarrow{K_{n+i}K_{c_i}}.$$接下来有 次询问,每次给出一个点集,判断这些点是否构成正多边形。
输入格式
第一行包含三个整数 ,满足
$$3\le n\le10^4,\qquad 0\le m\le3\cdot10^4,\qquad1\le k\le10^4.$$前 个点 按逆时针顺序构成一个非退化正多边形。输入只给出它们之间的结构关系,不需要给出具体平面坐标。
接下来 行,每行包含三个整数 ,满足
它们描述点 的构造方式。三个编号可以相同。
接下来 行,每行首先给出整数 ,随后给出 个点编号,表示询问的集合。满足
$$3\le r_i\le3\cdot10^4,\qquad1\le P_j^{(i)}\le n+m.$$所有询问中的点数之和不超过 。同一次询问中的点编号可以重复。
输出格式
输出 行。若第 个点集构成正多边形,输出 Yes,否则输出 No。大小写不敏感。
样例输入1
3 6 8
1 2 3
3 1 4
5 4 3
3 1 2
4 5 3
4 5 2
6 4 7 6 5 1 2
3 1 3 2
3 1 1 8
4 2 5 6 7
3 2 1 4
3 6 5 9
3 4 7 9
4 1 3 2 8
样例输出1
Yes
Yes
Yes
No
No
No
Yes
No