CF1569D.Inconvenient Pairs

There is a city that can be represented as a square grid with corner points in $(0, 0)$ and $(10^6, 10^6)$.

The city has $n$ vertical and $m$ horizontal streets that goes across the whole city, i. e. the $i$-th vertical streets goes from $(x_i, 0)$ to $(x_i, 10^6)$ and the $j$-th horizontal street goes from $(0, y_j)$ to $(10^6, y_j)$.

All streets are bidirectional. Borders of the city are streets as well.

There are $k$ persons staying on the streets: the $p$-th person at point $(x_p, y_p)$ (so either $x_p$ equal to some $x_i$ or $y_p$ equal to some $y_j$, or both).

Let's say that a pair of persons form an inconvenient pair if the shortest path from one person to another going only by streets is strictly greater than the Manhattan distance between them.

Calculate the number of inconvenient pairs of persons (pairs $(x, y)$ and $(y, x)$ are the same pair).

Let's recall that Manhattan distance between points $(x_1, y_1)$ and $(x_2, y_2)$ is $|x_1 - x_2| + |y_1 - y_2|$.

存在一座城市，其形状可表示为一个正方形网格，左下角和右上角的坐标分别为 $(0, 0)$ 和 $(10^6, 10^6)$。

该城市共有 $n$ 条纵向街道和 $m$ 条横向街道，贯穿整座城市：第 $i$ 条纵向街道从 $(x_i, 0)$ 延伸至 $(x_i, 10^6)$；第 $j$ 条横向街道从 $(0, y_j)$ 延伸至 $(10^6, y_j)$。

所有街道均为双向通行。城市的边界本身也视为街道。

有 $k$ 个人位于街道上：第 $p$ 个人位于点 $(x_p, y_p)$（即满足 $x_p = x_i$（对某个 $i$）或 $y_p = y_j$（对某个 $j$），或两者同时成立）。

我们称一对人构成不便对（inconvenient pair），当且仅当他们之间仅沿街道行走的最短路径长度严格大于他们之间的曼哈顿距离。

请计算不便对的人数（注意：$(x, y)$ 与 $(y, x)$ 视为同一对）。

回顾：两点 $(x_1, y_1)$ 与 $(x_2, y_2)$ 之间的曼哈顿距离定义为 $|x_1 - x_2| + |y_1 - y_2|$。

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains three integers $n$, $m$ and $k$ ($2 \le n, m \le 2 \cdot 10^5$; $2 \le k \le 3 \cdot 10^5$) — the number of vertical and horizontal streets and the number of persons.

The second line of each test case contains $n$ integers $x_1, x_2, \dots, x_n$ ($0 = x_1 \lt x_2 \lt \dots \lt x_{n - 1} \lt x_n = 10^6$) — the $x$-coordinates of vertical streets.

The third line contains $m$ integers $y_1, y_2, \dots, y_m$ ($0 = y_1 \lt y_2 \lt \dots \lt y_{m - 1} \lt y_m = 10^6$) — the $y$-coordinates of horizontal streets.

Next $k$ lines contains description of people. The $p$-th line contains two integers $x_p$ and $y_p$ ($0 \le x_p, y_p \le 10^6$; $x_p \in {x_1, \dots, x_n}$ or $y_p \in {y_1, \dots, y_m}$) — the coordinates of the $p$-th person. All points are distinct.

It guaranteed that sum of $n$ doesn't exceed $2 \cdot 10^5$, sum of $m$ doesn't exceed $2 \cdot 10^5$ and sum of $k$ doesn't exceed $3 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n, m \le 2 \cdot 10^5$；$2 \le k \le 3 \cdot 10^5$）—— 分别表示竖直街道和水平街道的数量，以及人员数量。

每个测试用例的第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$（$0 = x_1 \lt x_2 \lt \dots \lt x_{n - 1} \lt x_n = 10^6$）—— 表示竖直街道的 $x$ 坐标。

第三行包含 $m$ 个整数 $y_1, y_2, \dots, y_m$（$0 = y_1 \lt y_2 \lt \dots \lt y_{m - 1} \lt y_m = 10^6$）—— 表示水平街道的 $y$ 坐标。

接下来的 $k$ 行描述人员信息。第 $p$ 行包含两个整数 $x_p$ 和 $y_p$（$0 \le x_p, y_p \le 10^6$；且满足 $x_p \in \{x_1, \dots, x_n\}$ 或 $y_p \in \{y_1, \dots, y_m\}$）—— 表示第 $p$ 个人的坐标。所有点互不相同。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，$m$ 的总和不超过 $2 \cdot 10^5$，$k$ 的总和不超过 $3 \cdot 10^5$。

For each test case, print the number of inconvenient pairs.

对于每个测试用例，输出不方便的点对的数量。

The second test case is pictured below:

For example, points $3$ and $4$ form an inconvenient pair, since the shortest path between them (shown red and equal to $7$) is greater than its Manhattan distance (equal to $5$).

Points $3$ and $5$ also form an inconvenient pair: the shortest path equal to $1000001$ (shown green) is greater than the Manhattan distance equal to $999999$.

But points $5$ and $9$ don't form an inconvenient pair, since the shortest path (shown purple) is equal to its Manhattan distance.

第二个测试用例如下图所示：

例如，点 $3$ 和点 $4$ 构成一对“不便点对”，因为它们之间的最短路径（图中以红色标出，长度为 $7$）大于其曼哈顿距离（等于 $5$）。

点 $3$ 和点 $5$ 同样构成一对“不便点对”：其最短路径长度为 $1000001$（图中以绿色标出），大于其曼哈顿距离 $999999$。

但点 $5$ 和点 $9$ 并不构成“不便点对”，因为它们之间的最短路径（图中以紫色标出）等于其曼哈顿距离。