题目描述

索维尔与其邻国诺兰之间爆发了一场毁灭性的战争，这场战争已持续数百年。两国的边界可以表示为一条水平的直线 $y = 0$，其中 $y < 0$ 的区域属于索维尔，$y > 0$ 的区域属于诺兰。

诺兰在位置 $(x_i, y_i)$（$y_i > 0$）部署了 $N$ 门火炮。此外，诺兰还修建了 $M$ 道防御墙。每道防御墙可以表示为一个三元组 $\langle x_{j1}, x_{j2}, y_j \rangle$，即一条从 $(x_{j1}, y_j)$ 到 $(x_{j2}, y_j)$ 的水平线段，其中 $x_{j1} < x_{j2}$ 且 $y_j > 0$。索维尔已知，诺兰的火炮不会位于任何防御墙（包括其端点）上，且没有两门火炮位于同一位置。另外，也没有两道墙（包括其端点）有公共点。

索维尔决定建造一座瞭望塔，以观察诺兰火炮的任何可疑活动。由于建造一座瞭望塔的成本对于索维尔来说几乎是天文数字，他们只能负担得起一座。因此，他们提出了 $Q$ 个候选位置 $(x_k, y_k)$（$y_k < 0$）来建造瞭望塔。如果瞭望塔建在 $(x, y)$，则所有位于从 $(x, y)$ 出发的 视线 上的火炮都能被瞭望塔观察到（即可见）。一个位置 $(x_i, y_i)$ 位于从 $(x, y)$ 出发的视线上，当且仅当连接 $(x_i, y_i)$ 和 $(x, y)$ 的直线不与任何防御墙（包括其端点）相交；换句话说，不存在点 $(x', y')$ 同时位于某道防御墙上和线段 $(x_i, y_i)$ 与 $(x, y)$ 之间。注意，一门火炮不会影响其他火炮从瞭望塔观察的可见性。

本题的任务是，对于每个提出的瞭望塔候选位置，确定能够从该位置观察到的诺兰火炮的数量。

输入格式

输入的第一行包含三个整数：$N$、$M$ 和 $Q$（$1 \leq N \leq 40000$；$0 \leq M \leq 5$；$1 \leq Q \leq 40000$），分别表示火炮的数量、防御墙的数量以及瞭望塔候选位置的数量。接下来的 $N$ 行，每行包含两个整数：$x_i$ 和 $y_i$（$-10^6 \leq x_i \leq 10^6$；$0 < y_i \leq 10^6$），表示第 $i$ 门火炮的位置，其中 $i = 1 \ldots N$。接下来的 $M$ 行，每行包含三个整数：$x_{j1}$、$x_{j2}$ 和 $y_j$（$-10^6 \leq x_{j1} < x_{j2} \leq 10^6$；$0 < y_j \leq 10^6$），表示第 $j$ 道防御墙的位置，其中 $j = 1 \ldots M$。接下来的 $Q$ 行，每行包含两个整数：$x_k$ 和 $y_k$（$-10^6 \leq x_k \leq 10^6$；$-10^6 \leq y_k < 0$），表示一个瞭望塔的候选位置。

输出格式

对于每个输入的瞭望塔候选位置，按输入顺序，输出一行一个整数，表示从该候选位置能观察到的诺兰火炮数量。

6 2 3
0 2
0 15
5 7
15 15
35 12
45 10
5 20 5
25 40 10
0 -5
5 -10
20 -15

4
3
2

提示

样例输入/输出的解释

所有火炮、防御墙和瞭望塔候选位置如下图所示。

:::align{center} :::

• 第一个瞭望塔候选位置 $(0, -5)$ 可以观察到 $4$ 门火炮，即位于 $(0, 2)$、$(0, 15)$、$(5, 7)$ 和 $(45, 10)$ 的火炮。
• 第二个瞭望塔候选位置 $(5, -10)$ 可以观察到 $3$ 门火炮，即位于 $(0, 2)$、$(0, 15)$ 和 $(45, 10)$ 的火炮。
• 第三个瞭望塔候选位置 $(20, -15)$ 可以观察到 $2$ 门火炮，即位于 $(0, 2)$ 和 $(45, 10)$ 的火炮。

翻译由 DeepSeek V3.2 完成