Mountains Beyond Mountains

Time limit1sMemory limit64 MB

Summary

Given column heights, a highway row, and pier rules, print the N by M picture of rock, tunnel, bridge, and pier cells exactly as specified.

Level: Easy3 of 10
Topics: Simulation, Implementation, Matrix
Solved: No attempts yet

Problem

The Great Wall, the Eiffel Tower, the Burj Khalifa: Constructor's High (CH Inc.) had a hand in every famous building in the world. The company just finished an enormous highway and is getting ready to show it to the public.

Beomsu, an employee of CH Inc., was given the job of drawing one large picture of the highway. The picture is a digital image of $N \times M$ pixels, and it holds a wide mountain range with the highway cutting straight across it.

Beomsu draws on an empty image filled with '.' (ASCII 46). All he was handed is the height of the mountains and the height of the highway.

The mountain profile is $M$ non-negative integers $H_1, H_2, \dots, H_M$ . Column $i$ from the left is taken up by rock from the ground to height $H_i$ , and rock is printed as '#' (ASCII 35).

The highway takes up the row at height $X$ , the $X$ -th row from the bottom. If the mountain in the column the highway passes through is at least $X$ high, the highway is built as a tunnel there and is printed as '*' (ASCII 42). If the mountain in that column is lower than $X$ , the highway is built as a bridge there and is printed as '-' (ASCII 45).

When a bridge is built at the $i$ -th position from the left and $i$ is a multiple of 3, a pier must be built at that position. The pier runs from height $X - 1$ down to the pixel just above the rock, and it is printed as '|' (ASCII 124).

The picture Beomsu finished yesterday is gone, because Jaehyeon moved it to the trash and emptied it. Draw the large picture again in his place.

Input

The first line has two positive integers $N$ and $M$ ( $2 \le N, M \le 100\,000$ , $4 \le N \times M \le 200\,000$ ) giving the size of the image, then the height of the highway $X$ ( $1 < X \le N$ ), separated by spaces. The second line has $M$ integers $H_1, H_2, \dots, H_M$ ( $0 \le H_i \le N$ ) giving the mountain heights, separated by spaces.

Output

Print Beomsu's large picture on $N$ lines. The $r$ -th line from the top is the row at height $N - r + 1$ , and each line has exactly $M$ characters.

Examples2

Example 1

Input

8 10 5
1 4 2 3 7 8 2 5 3 0

Expected output

.....#....
....##....
....##....
----**-*--
.#|.##.#|.
.#|###.##.
.########.
#########.

Example 2
Input
```
6 3 6
0 0 0
```
Expected output
```
---
..|
..|
..|
..|
..|
```