Denis 在 SIS 召开几何匿名俱乐部会议。他为俱乐部准备了$$$n$$$个凸多边形,编号从$$$1$$$到$$$n$$$。他计划让俱乐部成员计算这些多边形的闵可夫斯基和。更准确地说,他计划给 $$$q$$$ 任务,其中第 $$$i$$$ 要求计算索引从 $$$l_i$$$ 到 $$$r_i$$$ 的多边形的 Minkowski 总和。
两个集合 $$$A$$$ 和 $$$B$$$ 的 Minkowski 之和是集合 $$$C = \{a + b : a \in A, b \in B\}$$$。可以证明,如果$$$A$$$和$$$B$$$是凸多边形,那么$$$C$$$也将是凸多边形。
两个凸多边形的总和
要计算 $$$p$$$ 多边形 ($$$p > 2$$$) 的 Minkowski 和,您需要计算前 $$$p - 1$$$ 多边形的 Minkowski 和,然后计算结果多边形和第 $$$p$$$ 个多边形的 Minkowski 和。
为了方便检查答案,Denis决定为他准备的每个任务准备并计算Minkowski和中的顶点数。帮助他做到这一点。
输入
输入的第一行包含一个整数 $$$n$$$ — Denis 准备的凸多边形的数量 ($$$1 \le n \le 100\,000$$$)。
然后是 $$$n$$$ 凸多边形。第 $$$i$$$ 个多边形的描述以一个整数 $$$k_i$$$ 开始 — 第 $$$i$$$ 个多边形中的顶点数 ($$$3 \le k_i$$$)。接下来的 $$$k_i$$$ 行包含两个整数 $$$x_{ij}$$$、$$$y_{ij}$$$ — 每个为逆时针顺序第 $$$i$$$ 个多边形的顶点坐标 ($$$|x_{ij}|, |y_{ij}| \le 10 ^ 9$$$)。
保证不存在三个连续的顶点位于同一条线上。所有多边形的顶点总数不超过$$$300\,000$$$。
下面一行包含一个整数 $$$q$$$ — 任务数量 ($$$1 \le q \le 100\,000$$$)。接下来的 $$$q$$$ 行包含任务的描述。第 $$$i$$$ 任务的描述包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$)。
输出
对于每个任务,打印一个整数 - 索引从 $$$l_i$$$ 到 $$$r_i$$$ 的多边形 Minkowski 总和中的顶点数。
示例
输入 #1
3 3 0 0 1 0 0 1 4 1 1 1 2 0 2 0 1 3 2 2 1 2 2 1 3 1 2 2 3 1 3
输出 #1
5 5 6
注意
示例说明:
示例中的第一个、第二个和第三个多边形
第一个和第二个、第二个和第三个以及所有多边形的 Minkowski 和