Intrusion Detection System

Lately William started going out clubbing and, as a result, he became very interested in lasers and laser-related systems. This new expertise came in handy, now that some of the IOIT participant teams started harassing him and Giorgio trying to extort hints about the tasks!

William is now building an Intrusion Detection System (IDS) to ensure that nobody can access their hotel room and steal classified information about the tasks.

William and Giorgio’s hotel room is $H$ meters long and $W$ meters wide. We can represent it as a $H \cdot W$ grid where each cell might contain a laser connector (which is both emitter and receiver).

In order for two connectors to “see” each other (and shoot lasers at each other) they must be lined up either horizontally or vertically: our lasers can’t go diagonally. Two connectors can’t see each other if there are other connectors “blocking the view”; the light beams, however, can intersect.

William has just designed a graph on the whiteboard, consisting of $N$ vertices and $M$ edges. He would like to introduce a laser connector on the grid for every vertex in the graph, and a laser beam (between two connectors) for every edge in the graph. We will call this a laser arrangement of the graph.

It’s always possible to find a complete laser arrangement (where all vertices and edges are used) for the graph designed by William. However, he will be happy enough with a partial arrangement: something is better than nothing, to stop those mischievous participants!

Input data

The first line contains integers $H$ and $W$. The second line contains integers $N$ and $M$. The following $M$ lines contain two integers each: $A_i$ and $B_i$, both of them between $0$ and $N - 1$, which represent a direct (and bidirectional) laser connection between vertex $A_i$ and vertex $B_i$.

Output data

You need to write the board you produced, that is: $H$ lines with $W$ integers each. The $j$-th integer of the $i$-th line will be either:

• A dot character . if the respective cell in the board is left empty.
• Some non-negative integer $u$, if you decide to put vertex $u$ in that cell.

Note that in a partial laser arrangement you don’t need to put all vertices in the grid: some may be ignored. That is: if you only print dots, it’s still a valid partial arrangement!

Moreover: if you want, you can put more spaces between cells for alignment purposes and they will be ignored. In the examples section we sometimes use two spaces instead of one.

Constraints and clarifications

• $1 \leq H, W \leq 1 \ 000$.
• $1 \leq N, M \leq 12$.
• $0 \leq A_i, B_i \leq N − 1$ for each $i = 0 \dots N − 1$.
• There are no self loops ($A_i = B_i$) and no duplicate edges.
• The graph may not be connected.

Your program will be tested against several test cases grouped in subtasks. The score in each subtask will be calculated as the minimum score obtained in any of its test cases, multiplied by the value of the subtask. The score in a test case will be calculated as: $\frac{M − \Delta_{out}}{M + 10 \cdot \Delta_{out}}$, where $\Delta_{out}$ is the difference between the number of connections established by your solution and $M$.

Example 1

stdin

2 3
4 4
0 1
2 3
2 1
0 3

stdout

0 3 .
1 2 .

Explanation

In the first sample case the presented solution is optimal.

Example 2

stdin

4 4
11 10
1 4
0 1
7 2
8 6
6 10
5 7
4 2
3 10
10 9
6 0

stdout

1 0 7 5
4 . 2 .
8 6 10 9
. . 3 .

Explanation

In the second sample case the presented solution is optimal.

Example 3

stdin

4 4
11 10
1 4
0 1
7 2
8 6
6 10
5 7
4 2
3 10
10 9
6 0

stdout

1 0 7 5
4 . 2 .
6 . 10 .
. . 3 9

Explanation

In the third sample case the presented solution establishes $7$ laser connections out of $10$, thus scoring: $\frac{10 - 3}{10 + 10 \cdot 3} = \frac{7}{40} = 0.175$ out of a maximum of $1$ point.