#P18126. Schoolgirls

Schoolgirls

Schoolgirls

Alice 学会了一种平行四边形工具:给定三个点 A,B,CA,B,C,她可以构造点 DD,使得有向向量 AB→\overrightarrow{AB} 与 DC→\overrightarrow{DC} 相等。三个输入点可以重合或共线。

称点 A1,A2,…,AnA_1,A_2,\dots,A_n(n≥3n\ge3)构成一个退化正多边形,当且仅当这些点全部重合。

称这些点按逆时针顺序构成一个非退化正多边形,当且仅当:

  • 所有点互不相同;
  • 它们位于同一个圆上;
  • 对圆心 OO,有
$$\angle A_1OA_2=\angle A_2OA_3=\cdots=\angle A_nOA_1=\frac{2\pi}{n},$$

且每次逆时针旋转 2π/n2\pi/n 都会把 OAi→\overrightarrow{OA_i} 变为 OA(i mod n)+1→\overrightarrow{OA_{(i\bmod n)+1}}。

若存在这些点的一个排列能按逆时针顺序构成非退化正多边形,也称这些点构成非退化正多边形。

只要点集构成上述两种正多边形之一,就称它构成正多边形。该定义与点的排列顺序无关。

最开始有 nn 个点,它们按逆时针顺序构成一个非退化正多边形。之后又用上述平行四边形工具构造了 mm 个点。第 n+in+i 个点 Kn+iK_{n+i} 使用此前三个点 Kai,Kbi,KciK_{a_i},K_{b_i},K_{c_i} 构造,满足

$$\overrightarrow{K_{a_i}K_{b_i}} = \overrightarrow{K_{n+i}K_{c_i}}.$$

接下来有 kk 次询问,每次给出一个点集,判断这些点是否构成正多边形。

输入格式

第一行包含三个整数 n,m,kn,m,k,满足

$$3\le n\le10^4,\qquad 0\le m\le3\cdot10^4,\qquad1\le k\le10^4.$$

前 nn 个点 K1,K2,…,KnK_1,K_2,\dots,K_n 按逆时针顺序构成一个非退化正多边形。输入只给出它们之间的结构关系,不需要给出具体平面坐标。

接下来 mm 行,每行包含三个整数 ai,bi,cia_i,b_i,c_i,满足

1≤ai,bi,ci≤n+i−1.1\le a_i,b_i,c_i\le n+i-1.

它们描述点 Kn+iK_{n+i} 的构造方式。三个编号可以相同。

接下来 kk 行,每行首先给出整数 rir_i,随后给出 rir_i 个点编号,表示询问的集合。满足

$$3\le r_i\le3\cdot10^4,\qquad1\le P_j^{(i)}\le n+m.$$

所有询问中的点数之和不超过 3⋅1043\cdot10^4。同一次询问中的点编号可以重复。

输出格式

输出 kk 行。若第 ii 个点集构成正多边形,输出 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