#539 초콜릿 프로그래밍 언어

문제

지문 언어

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

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

블록 간 이동

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

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

예를 들어, 아래 그림에서 P 명령을 실행한 후 이동할 위치는 $DP$ 와 $CC$ 의 상태에 따라 표시된 8가지 중 하나가 된다. $DP$ 가 오른쪽, $CC$ 가 왼쪽이면 1로 이동하며, $DP$ 가 아래, 가 오른쪽이면 4로 이동하게 된다.

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

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

입력

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

출력

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

제한

제출한 코드가 다음 중 하나에 해당하는 경우에는 코드의 출력과 상관없이 "틀렸습니다"를 받는다.

코드의 가로와 세로 크기의 곱이 1,000,000을 초과
어떤 입력에 대해 명령이 정의되지 않은 글자를 실행
어떤 입력에 대해 1,000,000개의 명령을 실행할 때까지 코드가 종료되지 않음
어떤 입력에 대해 성공적으로 수행된 r 명령의 $y$ 값의 합이 1,000,000을 초과

GitHub Gist 링크에서 초콜릿 언어의 인터프리터를 다운받아 실행해 볼 수 있다. 실행 방법은 chocolate.exe src.txt < input.txt 또는 python chocolate.py src.txt < input.txt 이다.

서브태스크

#	점수	제한
1	100	-

예제

입력

출력

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