Map Interface

Many public transit systems provide online interfaces for figuring out the route you want to take. One principle of good user interface design is that the system should show you all the relevant information, but no more, so you can focus on what matters. For a graphical interface showing a system map, this means showing a map that contains all the stations you will pass through, but as few extra stations as possible. On the other hand, most users are used to rectangular maps with a uniform scale, so we will stick with that.

Here is the problem more concretely. You are given the locations (as $(x, y)$ coordinates) of all stations in the system, and the list of stations (in order) that your line takes you through. Compute how many stations in total lie inside the smallest axis-aligned rectangle that contains your entire trip. A station on the boundary of the rectangle also counts as inside.

The first line contains the number of data sets $K$. This is followed by $K$ data sets, each of the following form:

• The first line contains two integers $n$ and $m$. Here $2 \le n \le 500$ is the total number of stations in the system, and $2 \le m \le n$ is the number of stations you travel through.
• The next $n$ lines each give two integers $x_i$ $y_i$, the coordinates of the $i$-th station. Stations are numbered from $1$ to $n$.
• The following line contains $m$ integers: the numbers of the stations you visit, in order.

For each data set, first output Data Set x: on a line by itself, where $x$ is its number starting from $1$. On the next line, output the total number of stations that lie inside the smallest rectangle containing your trip. Separate consecutive data sets with a single blank line.