Chocolate is a type of two-dimensional programming language. The following defines the operation of the Chocolate language.

In a Chocolate program, a block is defined as a connected set of identical characters (connected horizontally or vertically). Empty spaces (ASCII $32$) are not executed. The first block to be executed is the one containing the character at the top-left corner; if the top-left character is an empty space, the program does not execute.

Movement Between Blocks

To determine the next block to execute from the current block, two values, $DP$ and $CC$, are used. At the start of the program, $DP$ is initialized to Right, and $CC$ is initialized to Left. Simply put, $DP$ represents the direction of the program's progression (Right, Down, Left, Up), and $CC$ represents which side (leftmost or rightmost) of the block to select when looking in that direction. Given $DP$ and $CC$, the next block to be executed is determined as follows:

1. Among the characters in the current block, find the characters furthest in the $DP$ direction.
2. Among those characters, select the one at the extreme end in the $CC$ direction.
3. Move in the $DP$ direction from that character.

If the cell to move to is an empty space or outside the program area, the move is invalid, and the program attempts to find a valid move by changing $DP$ and $CC$ as follows:

1. Attempt to change $CC$ (if Left, change to Right; if Right, change to Left).
2. If still unable to move, rotate $DP$ clockwise by $90$ degrees and try again.
3. Continue changing $CC$ and $DP$ in this order until a valid direction is found or all $8$ combinations have been attempted.

If all $8$ combinations are attempted and no valid move is found, the program terminates. This is the only way for the program to terminate. (Runtime errors do not exist.)

Command List

In the Chocolate language, all data is stored in a single stack, and stack elements are signed 64-bit integers.

The Chocolate language has various commands, and each time a block is entered, the command corresponding to the character type of that block is executed. The following is the list of commands. For all commands, if the operation is impossible (e.g., insufficient integers on the stack, division by zero, no input character available), nothing happens and the program continues to execute.

• I: Read $1$ character from stdin and push its ASCII code onto the stack. If there are no more characters to read, ignore the command.
• O: Pop an integer from the stack and output the character whose ASCII code is the remainder of the integer divided by $256$ (a value between $0$ and $255$ inclusive) to stdout.
• P: Push an integer representing the area of the current block onto the stack.
• p: Pop and discard an integer from the stack.
• +: Pop integers $x$ and $y$ from the stack and push $y+x$ onto the stack.
• -: Pop integers $x$ and $y$ from the stack and push $y-x$ onto the stack.
• *: Pop integers $x$ and $y$ from the stack and push $y \times x$ onto the stack.
• /: Pop integers $x$ and $y$ from the stack and push $\lfloor y/x \rfloor$ onto the stack.
• %: Pop integers $x$ and $y$ from the stack and push $y\%x$ onto the stack. This value satisfies $\lfloor y/x \rfloor \times x + y\%x = y$.
• !: Pop an integer $x$ from the stack; if $x$ is $0$, push $1$, otherwise push $0$.
• >: Pop integers $x$ and $y$ from the stack; if $y>x$, push $1$, otherwise push $0$.
• D: Pop an integer $x$ from the stack and rotate $DP$ clockwise by $90$ degrees $x$ times. If $x$ is negative, rotate in the opposite direction $-x$ times.
• C: Pop an integer $x$ from the stack and flip $CC$ $|x|$ times.
• d: Pop an integer $x$ from the stack and push $x$ onto the stack twice.
• r: Pop integers $x$ and $y$ from the stack, then "rotate" the top $y$ elements of the stack $x$ times. A rotation moves the top element to the bottom and shifts the others up by one position. If $x$ is negative, repeat the opposite operation $-x$ times. If $y \le 0$ or $y$ is greater than the number of elements remaining in the stack after popping $x$ and $y$, do not perform the rotation and push $y$ and $x$ back onto the stack.

The following is an example of Chocolate language code that prints Hello World!:

PPPPPPdP+*d
PP        dO
  Ppd+PPd* Od
 dd    P -- dP
OO dOPPd+ ++ P
d ++  P +- P /
* P PP/O d p +
+ P P OO O P d
P P O   PP p P
PPO d-+dPP dPP
P d+  P   POPP
dP +*+PdPPP PP
 PP  P     --
  PO+PPOdOdO

Now, solve the following problem using the Chocolate language.

Input

An integer $N$ ($1 \le N \le 100$) is given. There is a newline (ASCII code 10) at the end of the input.

Output

Print stars (ASCII code 42) from the first line to the $N$-th line. On the $i$-th line, print $i$ stars without spaces. Note that you must print a newline (ASCII code 10) between lines.

Examples

Input 1

5

Output 1

*
**
***
****
*****

Note

Languages available for submission: Text

Code exceeding 524,288B in length cannot be submitted. If the product of the code's width and height exceeds 1,000,000, or if the code does not terminate after executing 1,000,000 commands for a single input, it will be judged as "Wrong Answer".