Problem Description

DEGwer owns a land in the plane of the range $[-W, W] \times [-H, H]$ and is engaged in agriculture here. Troubled by wildlife damage, DEGwer decided to install beams to burn off any animals that intrude into the land. Specifically, he will erect pillars with either a $+$ or $-$ sign at lattice points within the land, and connect pillars with different signs with beams. However, if beams intersect at points without pillars, the energy of the beams will resonate and cause trouble, so beams must not share points without pillars.

DEGwer has already decided on $ N $ lattice points $(X_i, Y_i) (i = 1, 2, \dots, N)$ where the pillars will be erected. All four corners of the land are included, and no three points are collinear. Determine the signs of each pillar and the pairs of pillars to connect with beams to maximize the number of beams.

Input Format

The input is given from the standard input in the following format:

$W\ H$ $ N $ $X_1\ Y_1$ $X_2\ Y_2$ $\vdots$ $X_N\ Y_N$

Output Format

Output the method to maximize the number of beams in the following format:

$ S $ $ M $ $P_1\ Q_1$ $P_2\ Q_2$ $\vdots$ $P_M\ Q_M$

• $ S $ is a string of length $ N $ consisting of + and -, where the $ i $-th character $ S_i $ represents the sign of the pillar at $ (X_i, Y_i) $.
• $ M $ is an integer representing the maximum number of beams.
• For each $i = 1, 2, \dots, M$, $ (P_i, Q_i) $ represents connecting a beam between pillar $ P_i $ and pillar $ Q_i $, and it must hold that $S_{P_i} \neq S_{Q_i}$.
• For $i \neq j$, the line segment connecting $ (X_{P_i}, Y_{P_i}) $ and $ (X_{Q_i}, Y_{Q_i}) $ does not intersect with the line segment connecting $ (X_{P_j}, Y_{P_j}) $ and $ (X_{Q_j}, Y_{Q_j}) $ except at their endpoints.

Sample Input and Output

Sample Input #1

1 1
4
1 1
-1 1
-1 -1
1 -1

Sample Output #1

+-+-
4
1 2
2 3
3 4
4 1

Sample Input #2

1 2
5
1 2
-1 2
0 1
-1 -2
1 -2

Sample Output #2

+-++-
6
1 2
2 4
4 5
5 1
2 3
3 5

Notes/Hints

Constraints

• $1 \le W \le 10^9$
• $1 \le H \le 10^9$
• $4 \le N \le 10^5$
• $-W \le X_i \le W (1 \leq i \leq N)$
• $-H \le Y_i \le H (1 \leq i \leq N)$
• $(X_i, Y_i) \neq (X_j, Y_j) (i \neq j)$
• There exists an $ i $ such that $(X_i, Y_i) = (\pm W, \pm H)$ (signs can be arbitrary).
• For $i \neq j \neq k \neq i$, $ (X_i, Y_i), (X_j, Y_j), (X_k, Y_k) $ are not collinear.

Sample Explanation 1

DEGwer's land is $[-1, 1] \times [-1, 1]$, and pillars are erected only at the four corners. By assigning alternating different signs to the pillars in a (counter)clockwise manner, beams can be installed between all adjacent pillars, which is the maximum.

Sample Explanation 2

DEGwer's land is $[-1, 1] \times [-2, 2]$, and pillars are erected at the four corners and the lattice point $ (0, 1) $. By assigning alternating different signs to the pillars at the corners in a (counter)clockwise manner and an arbitrary sign to the pillar at $ (0, 1) $, 6 beams can be installed as in the output example. It can also be proven that no more than 7 beams can be installed, making this the maximum and an example of the answer.

见题面 Input 部分

见题面 Output 部分