Circuit Layout and Routing

This problem is about a simplified circuit layout problem on an n × m grid. Some cells are blocked (marked with a #), some cells are mandatory wiring (marked with a +) and the rest (marked with a .) can be optionally wired by converting them into +.

Your task is to choose as many of the optional cells as possible to be wired (i.e. change . to +) under the following constraints:

1. The final set of wired cells (both the originally mandatory ones and the ones you choose) must be connected. In other words, any wired cell must be reachable from any other wired cell via moves up, down, left or right (through other wired cells).
2. The wiring must not contain any cycles (short circuits). Formally, there should be no sequence of distinct wired cells c₁, c₂, ..., c_k with k > 2 such that for every 1 ≤ i < k the cells c_i and c_i+1 are adjacent (neighbors in the grid) and additionally c_k is adjacent to c₁. Equivalently, the induced subgraph of wired cells should form a tree.

You are guaranteed that there is at least one mandatory wired cell (a cell marked +) in the input. Note that if an optional cell is not selected for wiring, it remains as .. The blocked cells (#) cannot be wired.

Example:

Input:
#....#
....+#
.+####
.+...#
A possible valid wiring solution is:
#++.+#
.++++#
++##+#
++++.#
In the above solution, all wired cells are connected and no cycle exists, while as many optional cells as possible are utilized.

</p>

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 1000) representing the number of rows and columns of the grid. This is followed by n lines, each containing exactly m characters. Each character is one of:

• # indicating a blocked cell (cannot be wired),
• + indicating a cell that must be wired, or
• . indicating an optional cell, which you can decide to wire (by turning it into +) or leave unused.

It is guaranteed that there is at least one cell marked + in the grid.

outputFormat

Output the final grid of the same size where each cell is one of:

• # for blocked cells,
• + for wired cells (both mandatory and selected optional cells), or
• . for optional cells that were not wired.

The output must satisfy the constraints: the wired cells form a connected acyclic (tree) subgraph, and you should maximize the number of optional cells you convert to wired cells subject to these restrictions.

sample

#....#
....+#
.+####
.+...#

#++.+#
.++++#
++##+#
++++.#

</p>