Chocolate is a two-dimensional programming language. How it works is described below.

In Chocolate, identical characters adjacent horizontally or vertically form a block, and such blocks are the unit of operation. Spaces (ASCII 32) are ignored. The first block to be executed is the block containing the leftmost character of the first line. If it is a space, the program does not run.

Moving across blocks

Two values $DP$ and $CC$ determine the next block to run. $DP$ represents the direction forward (right, down, left, or up), and looking in that direction, $CC$ chooses either the leftmost or the rightmost block on that side. When program starts, $DP$ is right and $CC$ is left. Given the current values of $DP$ and $CC$, the next block to run is determined as follows:

1. Among the characters in the current block, find the farthest ones in the direction of $DP$.
2. Among them, choose the one that is the farthest in the direction of $CC$ while looking in the direction of $DP$.
3. Move out of that character in the direction of $DP$.

For example, in the image below, the next block to move after running the P block can be one of 8 different blocks, labelled 1 through 8. If $DP$ is right and $CC$ is left, the destination is 1. If $DP$ is down and $CC$ is right, the destination is 4.

If the position to move next is blank or out of program space, then such a move is not valid, and $DP$ and $CC$ are changed as follows until a valid move is found.

이때 이동할 칸이 빈 칸이거나 프로그램 영역 밖이면 이동할 수 없으며, 다음과 같이 $DP$와 $CC$를 바꿔가며 이동할 칸을 찾는다.

1. Try switching $CC$ first. If is currently left, change it to right; otherwise, change it to left.

An integer $N$ is given. ($1 \le N \le 100$)

The input ends with a newline (ASCII 10).

Over $N$ lines, print asterisks (ASCII 42). On the $i$-th line, print $i$ asterisks without blanks. Don't forget to print newlines (ASCII 10) between two lines.

The verdict will be Wrong Answer when at least one of the following is true:

• the product of the width and the height of the code is over 1,000,000
• for some input, an undefined instruction is executed
• for some input, the program does not terminate until 1,000,000 commands are run
• for some input, the sum of $y$ values of succesful r commands exceeds 1,000,000

Interpreters in C++ and Python are available at GitHub Gist. How to run: chocolate.exe src.txt < input.txt or python chocolate.py src.txt < input.txt