TASK: optimal_placement
REV: January 06, 2024

+---------+
|STATEMENT|
+---------+

There exists a grid of size N by N. You are given M flags to place on the grid,
numbered from 1 to M. A flag numbered i can be placed either on (x_i, y_i) or
(w_i, z_i). After you place all the flags on the grid, the "covering score"
of the grid is defined as the minimum of distance between any two distinct flags
.

The distance between flag positioned at (x, y) and (x2, y2) is defined as
|x - x2| + |y - y2|. Note that |v| means the absolute value of v.

We call a placement of flags "optimal" if there is no placement with greater
"covering score".

Your task is to find any optimal placement.

+-----------+
|CONSTRAINTS|
+-----------+

- N and M are positive integers not exceeding 2000 and 500 respectively.

- M is more than one

- N * N >= 2 * M

- x_i, y_i, w_i, z_i are integer not less than 1 and not more than N

- (x_i, y_i) != (w_j, z_j) for all i, j
- (x_i, y_i) != (x_i, x_i) for all i
- (w_i, w_i) != (w_i, w_i) for all i

+-----+
|INPUT|
+-----+

The first line consist of two integers: N M
The following M lines consist of four integers.
        Where i-th line is made of x_i, y_i, w_i, z_i.

+------+
|OUTPUT|
+------+

In the first line, print the covering score of the optimal placement found.
In the second , print a string of length M to report which option was selected for each flag.
        That is in for each flag, print "A" if i-th flag was placed at (x_i, y_i)
                and "B" if i-th flag was placed at (w_i, z_i).
        Please do not use whitespace to seperate the option each flags.


+------+
|SAMPLE|
+------+

input#1:
3 2
2 3 2 1
3 1 1 1

output#1:
3
AB

note:
in the above sample, AA would also be a valid answer


Author: sleepntsheep