The competition venue is divided into a grid of $r$ rows and $c$ columns, where each workstation is located within a grid cell. Surveillance cameras are located at the $(r + 1) \times (c + 1)$ intersections of the grid lines. Horizontal grid lines are numbered $0$ to $r$ from top to bottom, and vertical grid lines are numbered $0$ to $c$ from left to right. The position of each camera can be represented by its grid line coordinates as a tuple $(x, y)$. Each camera can face one of four directions: "top-right", "top-left", "bottom-left", or "bottom-right", numbered $1$ to $4$ respectively, corresponding to the quadrants. The monitoring range for each direction is shown in the figure below.

$$\begin{matrix}2&1\\3&4\end{matrix}$$

Due to constraints on wiring and signals, the orientation of each camera must be chosen from a specific set $S$, where $S \subseteq \{ 1, 2, 3, 4 \}$.

Venue Surveillance Problem: Given the grid dimensions, the positions of the cameras $(x_i, y_i)$, and the set of allowed orientations $S$, calculate the maximum number of workstations that can be monitored in this environment.

Input

The input file provides multiple test cases.

The first line contains a positive integer $k$, representing the size of the set $S$.

The second line contains the elements of the set $S$ in ascending order.

The third line contains a positive integer $t$, representing the number of test cases.

For each test case:

The first line contains three positive integers $n, r, c$, representing $n$ cameras in the venue and a grid of $r$ rows and $c$ columns.

The next $n$ lines each contain two positive integers $x_i, y_i$, representing the position of the $i$-th camera at $(x_i, y_i)$.

Output

For each test case, output the maximum number of workstations that can be monitored in the corresponding environment. Output each result on a new line.

Examples

Input 1

4
1 2 3 4
1
3 6 8
4 2
1 4
5 6

Output 1

44

Subtasks

For $100\%$ of the test data, $n \leq 10^5$, $0 \leq x_i \leq r \leq 10^9$, and $0 \leq y_i \leq c \leq 10^9$.

For $100\%$ of the test data, $\sum n \leq 10^5$.