초콜릿은 2차원 프로그래밍 언어의 일종이다. 아래는 초콜릿 언어의 동작 정의이다.

초콜릿 프로그램에서는 같은 글자가 상하좌우로 연결된 블록이 실행 단위이다. 빈 칸(아스키 $32$)은 실행되지 않는다. 맨 처음 실행되는 블록은 맨 왼쪽 위의 글자가 포함된 블록이며, 맨 왼쪽 위 글자가 빈 칸이면 프로그램이 실행되지 않는다.

블록 간 이동

한 블록에서 다음 실행할 블록을 결정하기 위해 $DP$와 $CC$의 두 가지 값이 존재한다. 프로그램 시작 시에 $DP$는 오른쪽, $CC$는 왼쪽으로 초기화된다. 간단히 설명하면 $DP$는 프로그램의 진행 방향(오른쪽, 아래, 왼쪽, 위)을 나타내며, $CC$는 그 방향을 바라봤을 때 어느 쪽 (맨 왼쪽이나 오른쪽) 블록을 선택할지를 나타낸다. $DP$와 $CC$가 주어졌을 때 다음 실행될 블록은 다음과 같이 결정된다.

1. 현재 블록의 글자들 중에서 $DP$의 방향으로 가장 멀리 있는 글자들을 찾는다.
2. 그 글자들 중에서 $CC$의 방향으로 가장 끝에 있는 글자를 고른다.
3. 그 글자에서 $DP$ 방향으로 이동한다.

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

1. $CC$를 왼쪽이면 오른쪽으로, 오른쪽이면 왼쪽으로 바꿔서 시도한다.
2. 그래도 이동할 수 없으면 $DP$를 시계 방향으로 $90$도 돌려서 다시 시도한다.
3. 이동할 수 있는 방향을 찾거나 $8$가지 조합을 모두 시도할 때까지 $CC$와 $DP$ 순서로 바꾸기를 계속 시도한다.

$8$가지 조합을 모두 시도했는데 이동할 곳이 없으면 프로그램이 종료된다. 이것이 프로그램이 종료되는 유일한 방법이다. (런타임 에러는 존재하지 않는다.)

명령 목록

초콜릿 언어에서 모든 데이터는 하나의 스택에 저장되고, 스택의 원소는 signed 64비트 정수이다.

초콜릿 언어에는 여러 가지 명령이 있으며, 각 블록에 진입할 때마다 그 블록의 글자 종류에 해당하는 명령이 실행된다. 다음은 명령의 목록이다. 모든 명령에 대해서, 동작이 불가능한 경우 (스택에 정수가 부족하거나 0으로 나누는 경우, 입력받을 글자가 없는 경우 등) 아무 일도 일어나지 않고 프로그램이 계속 실행된다.

• I: stdin에서 1글자를 입력받아 그 글자의 아스키 코드를 스택에 넣는다. 더 이상 받을 글자가 없으면 무시한다.
• O: 스택에서 정수 하나를 꺼내 $256$으로 나눈 나머지(0 이상 255 이하의 값)를 아스키 코드로 갖는 글자를 stdout으로 출력한다.
• P: 현재 영역의 면적에 해당하는 정수를 스택에 넣는다.
• p: 스택에서 정수 하나를 꺼내 버린다.
• +: 스택에서 정수 $x$, $y$를 꺼내 $y+x$를 스택에 넣는다.
• -: 스택에서 정수 $x$, $y$를 꺼내 $y-x$를 스택에 넣는다.
• *: 스택에서 정수 $x$, $y$를 꺼내 $y \times x$를 스택에 넣는다.
• /: 스택에서 정수 $x$, $y$를 꺼내 $\lfloor y/x \rfloor$를 스택에 넣는다.
• %: 스택에서 정수 $x$, $y$를 꺼내 $y\%x$를 스택에 넣는다. 이 값은 $\lfloor y/x \rfloor \times x + y\%x = y$를 만족한다.
• !: 스택에서 정수 $x$를 꺼내 $x$가 $0$이면 $1$, 아니면 $0$을 스택에 넣는다.
• >: 스택에서 정수 $x$, $y$를 꺼내 $y>x$이면 $1$, 아니면 $0$을 스택에 넣는다.
• D: 스택에서 정수 $x$를 꺼내 $DP$를 $x$번 시계 방향으로 $90$도 회전한다. $x$가 음수이면 반대 방향으로 $-x$번 회전한다.
• C: 스택에서 정수 $x$를 꺼내 $CC$를 $|x|$번 반대로 바꾼다.
• d: 스택에서 정수 $x$를 꺼내 $x$를 스택에 두 번 넣는다.
• r: 스택에서 정수 $x$, $y$를 꺼낸 다음, 스택의 맨 위 $y$개 원소를 $x$번 "회전"한다. 여기서 회전이란, 가장 위에 있는 원소를 가장 아래로 이동하고 나머지를 한 칸씩 위로 올리는 동작이다. $x$가 음수이면 반대 동작을 $-x$번 반복한다. $y$가 $0$ 이하이거나, $x$와 $y$를 제거한 후의 스택의 길이보다 크면 회전 동작을 하지 않고 $y$와 $x$를 원래대로 다시 스택에 넣는다.

다음은 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

이제 초콜릿 언어로 아래의 문제를 풀어보자.

Input

정수 $N$ ($1 \le N \le 100$)이 주어진다. 입력 끝에는 줄바꿈(아스키 코드 10)이 있다.

Output

첫째 줄부터 $N$번째 줄까지 별(아스키 코드 42)을 출력한다. $i$번째 줄에는 빈 칸 없이 별을 $i$개 출력한다. 줄과 줄 사이에는 줄바꿈(아스키 코드 10)을 출력해야 함에 유의하라.

Examples

Input 1

5

Output 1

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

Note

제출할 수 있는 언어: Text

코드의 길이가 524,288B를 초과하는 코드는 제출할 수 없다. 코드의 가로와 세로 크기의 곱이 1,000,000을 초과하거나, 하나의 입력에 대해 1,000,000개의 명령을 실행할 때까지 코드가 종료되지 않으면 "틀렸습니다"를 받는다.