human
Can you solve the below in PYTHON3?
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|.

Input

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

The first line of each test case contains three integers n, m and k (2 ≤ n, m ≤ 2 ⋅ 10^5.
2 ≤ k ≤ 3 ⋅ 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, ..., x_n (0 = x_1 < x_2 < ... < x_{n - 1} < x_n = 10^6) — the x-coordinates of vertical streets.

The third line contains m integers y_1, y_2, ..., y_m (0 = y_1 < y_2 < ... < y_{m - 1} < 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 ≤ x_p, y_p ≤ 10^6.
x_p ∈ \\{x_1, ..., x_n\} or y_p ∈ \\{y_1, ..., y_m\}) — the coordinates of the p-th person. All points are distinct.

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

Output

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

Example

Input

2
2 2 4
0 1000000
0 1000000
1 0
1000000 1
999999 1000000
0 999999
5 4...
 ... Write me a Python program to print the number of inconvenient pairs?
assistant
#Here is Python program to print the number of inconvenient pairs.

try:
        import sys
        from functools import lru_cache, cmp_to_key
        from heapq import merge, heapify, heappop, heappush
        # from math import *
        from collections import defaultdict as dd, deque, Counter as C
        from itertools import combinations as comb, permutations as perm
        from bisect import bisect_left as bl, bisect_right as br, bisect, insort
        from time import perf_counter
        from fractions import Fraction
        import copy
        from copy import deepcopy
        import time
        starttime = time.time()
        mod = int(pow(10, 9) + 7)
        mod2 = 998244353

        def data(): return sys.stdin.readline().strip()
        def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
        def L(): return list(sp())
        def sl(): return list(ssp())
        def sp(): return map(int, data().split())
        def ssp(): return map(str, data().split())
        def l1d(n, val=0): return [val for i in range(n)]
        def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

        # sys.setrecursionlimit(int(pow(10,6)))
        # from sys import stdin
        # input = stdin.buffer.readline
        # I = lambda : list(map(int,input().split()))
        # import sys
        # input=sys.stdin.readline

        sys.stdin = open("input.txt", "r")
        sys.stdout = open("output.txt", "w")
except:
        pass


for _ in range(L()[0]):
        n, m, k = L()
        X = sorted(L())
        Y = sorted(L())

        dx = set(X)
        dy = set(Y)

        R = dd(dict)
        C = dd(dict)

        CntRow = CntCol = 0

        cy = dd(int)
        rx = dd(int)
        for i in range(k):
                xp, yp = L()
                if xp in dx and yp in dy:
                        continue
                if xp in dx:
                        y = br(Y, yp)

                        C[y][xp] = C[y].get( xp, 0 ) + 1
                        cy[y] +=1
                else:
                        x = br(X, xp)

                       ...