시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2.5 초 64 MB 1 1 1 100.000%

문제

Professor Zhang has an $n \times m$ matrix consisting of all zeroes. Professor Zhang changes $k$ elements of the matrix into 1s.

Given a permutation $p$ of $\{1, 2, 3, 4\}$, Professor Zhang wants to find the number of such submatrices that:

  • The number of 1s in the submatrix is exactly 4.
  • Let the positions of the 1s in the submatrix be $(r_1, c_1)$, $(r_2, c_2)$, $(r_3, c_3)$, and $(r_4, c_4)$. Then $r_1 < r_2 < r_3 < r_4$ and $(p_i - p_j) \cdot (c_i - c_j) > 0$ for all $1 \le i < j \le 4$.
  • no other submatrices inside the chosen submatrix meet the above two requirements.

입력

There are multiple test cases. The first line of input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains three integers $n$, $m$ and $k$ ($1 \le n, m, k \le 2000$): the size of the matrix and the number of 1s. The second line contains four integers $p_1, p_2, p_3, p_4$ denoting the permutation of $\{1, 2, 3, 4\}$.

Each of the next $k$ lines contains two integers $r_i$ and $c_i$ ($1 \le r_i \le n$, $1 \le c_i \le m$): the position of the $i$-th 1. No two 1s will be in the same position.

There are at most $250$ test cases, and the total size of the input is at most $250$ kibibytes.

출력

For each test case, output a single integer: the number of submatrices which meet all the requirements.

예제 입력 1

1
5 5 4
1 2 3 4
1 1
2 2
3 3
4 4

예제 출력 1

1