P5701 [CTSC1998] Bus Stop Sign Positions.

CTSC1998 D2T2.

A certain city downtown is planned as a grid. The downtown area is evenly divided by $n+1$ north-south main roads and $n+1$ east-west main roads into $n^2$ blocks and $(n+1)^2$ intersections. Both blocks and intersections are numbered **from top to bottom, and from left to right**. Now, several blocks are chosen as sightseeing areas. For each sightseeing area, there will be exactly one bus route that runs around its four sides, and this bus will set up four bus stops only at the four intersections surrounding that block. Two adjacent blocks (two blocks are adjacent if and only if they share a segment of road) will share two bus stops. The government sets up a stop sign for each bus stop. Stop sign numbers are distinct natural numbers $1, 2, \ldots$. However, assigning these numbers becomes a headache. This is because there are three bus companies in the city, each with its own rule: 1. For Company A, the four stops around a block must satisfy: starting from some stop, the three stop sign numbers encountered **clockwise** are **strictly decreasing**, and then it returns to the original stop. 2. For Company B, the four stops around a block must satisfy: starting from some stop, the three stop sign numbers encountered **counterclockwise** are **strictly decreasing**, and then it returns to the original stop. 3. For Company C, the four stops around a block must satisfy: starting from some stop, going clockwise, the stop sign numbers should **decrease, then increase, then decrease, then increase**, and then it returns to the original stop. To be fair, the government wants to find a way to assign stop sign numbers to all $K$ bus stops involved in these $m$ sightseeing blocks, so that the three companies can open as close as possible to the same number of bus routes among the sightseeing areas. Please write a program to solve this problem. Let the numbers of bus routes that the three companies can open be $X$, $Y$, and $Z$, respectively. You should make $S=(X-Y)^2+(Y-Z)^2+(Z-X)^2$ as small as possible.

The first line contains $n$. The second line contains $m$, meaning there are $m$ blocks that are sightseeing areas. The third line contains $m$ integers, which are the indices of these $m$ blocks, separated by one space.

The first line contains the value of $S$ you found. The second line contains $K$. In the next $K$ lines, each line contains two integers: the first is an intersection index, and the second is the stop sign number you assign to the bus stop at this intersection (the stop sign numbers should be distinct natural numbers from $1$ to $K$). These $K$ lines should be output in increasing order of the intersection index.

Constraints $1 \leq n \leq 7$ Translated by ChatGPT 5