Forest Picture

The game "Draw a forest picture" is popular among the younger visitors of the amusement park. The number of players is practically unlimited and nearly everybody wins. The rules are simple. A leader of the game briefly describes a forest picture he or she saw recently, then the players get paper and crayons and reproduce the image as well as they can. Everybody who hands in at least a partial image of any piece of any forest anywhere on Earth, drawn in any style, wins a small reward in the form of a chocolate or a fruit.

In this problem you implement an imitation of the game. Since you are much more experienced than the younger players, your drawing has to meet the specification exactly. The image you reproduce depicts a glade, an open area within a woodland that carries fewer trees than the thick forest around it. Print the image in the ascii art style.

An $M \times M$ image is represented by a canvas of $M$ rows, each row holding $M$ characters. Each pixel of the image is represented by one printable ASCII character on the canvas, and the coordinates of a pixel match the coordinates of its character on the canvas. The pixel in the bottom left corner of the image has coordinates $(0, 0)$ and the pixel in the top right corner has coordinates $(M-1, M-1)$. The $x$ coordinate of the pixel in the bottom right corner is $M-1$.

Each pixel of the image depicts grass, or a part of a standing tree, or a part of a tree stump. A pixel depicting grass is represented by a single dot . (ASCII code 46). Standing trees and stumps take more pixels, and their representation on the canvas follows.

A standing tree has a positive height $S$ and consists of four parts: the roots, the trunk, the branches and the treetop. The roots are three horizontally adjacent characters _|_ (ASCII codes 95, 124, 95). The trunk is $S$ vertically adjacent vertical bars | (ASCII code 124) placed immediately above the centre of the roots. The branches are $S$ left branches placed immediately to the left of the trunk and $S$ right branches placed immediately to the right of the trunk, and every branch touches the trunk. A left branch is a single forward slash / (ASCII code 47) and a right branch is a single backslash \ (ASCII code 92). The treetop is a single caret ^ (ASCII code 94) placed immediately above the topmost character of the trunk.

A tree stump is three horizontally adjacent pixels represented by _o_ (ASCII codes 95, 111, 95).

Depending on its coordinates, a standing tree or a stump may appear in the image only partially, or not at all.

The input holds several test cases and continues until the end of the file. Each case starts with a line containing two integers $M$ and $N$ separated by a space ($1 \le M \le 100$, $1 \le N \le 10^5$). The next $N$ lines each contain three integers $S$, $X$, $Y$ separated by spaces, describing one standing tree or one tree stump. $X$ and $Y$ are the coordinates of the centre of the roots or of the stump. If $S = 0$ the triple describes a stump, and if $S > 0$ it describes a standing tree of height $S$. It holds $0 \le S \le 9$ and $-10^9 \le X, Y \le 10^9$.

No two different standing trees or stumps have parts drawn on the same pixel.

For each test case print the canvas with the image of the glade. Print the top row of the canvas first and the bottom row last. Frame the printout with a square border of asterisks * (ASCII code 42) one pixel thick. The border has to touch the canvas, so there is no space between the border and the canvas, neither horizontally nor vertically. Print one empty line after each test case.