자물쇠 비밀번호

창고 문에 다이얼 자물쇠가 하나 달려 있다. 이 자물쇠의 비밀번호는 k+1자리이고, 각 자리에는 0부터 9까지의 숫자 가운데 하나가 들어간다. 이때 비밀번호의 각 자리에 들어가는 숫자는 서로 모두 다르다. 그래서 비밀번호의 자릿수는 열 자리를 넘을 수 없다.

자물쇠를 설치한 사람은 비밀번호를 잊지 않으려고 쪽지 하나를 남겨 두었다. 쪽지에는 이웃한 두 자리의 크기 관계를 나타내는 기호가 k개 적혀 있다. 왼쪽에서 i번째 기호는 i번째 자리의 숫자와 i+1번째 자리의 숫자를 견준 결과다. 기호가 <이면 왼쪽 자리의 숫자가 오른쪽 자리의 숫자보다 작고, >이면 왼쪽 자리의 숫자가 오른쪽 자리의 숫자보다 크다.

쪽지의 기호를 모두 만족하는 비밀번호는 여러 개 있을 수 있다. 기호 k개가 주어졌을 때, 조건을 만족하는 비밀번호 가운데 가장 큰 것과 가장 작은 것을 찾는 프로그램을 작성하여라. 비밀번호는 어느 것이나 k+1자리로 자릿수가 같으므로, 왼쪽부터 읽은 수가 더 큰 것이 더 큰 비밀번호다. 또한 첫째 자리에 0이 들어가는 비밀번호도 자물쇠에 그대로 쓸 수 있다.

예를 들어 k=2이고 쪽지에 적힌 기호가 다음의 표와 같다고 해보자.

이 경우 비밀번호는 세 자리이고, 첫째 자리가 둘째 자리보다 작으며, 둘째 자리가 셋째 자리보다 커야 한다. 조건을 만족하는 비밀번호 가운데 가장 큰 것과 가장 작은 것은 다음과 같다.

8은 9보다 작고 9는 7보다 크므로 897은 조건을 만족한다. 둘째 자리가 9보다 커질 수는 없고 첫째 자리가 8보다 커지면 둘째 자리와 겹치므로, 897보다 큰 비밀번호는 없다. 또한 0은 2보다 작고 2는 1보다 크므로 021도 조건을 만족한다. 021은 첫째 자리가 0이지만 세 자리 비밀번호로 그대로 쓸 수 있으므로, 앞의 0을 떼지 않고 021 그대로 내놓아야 한다.

입출력 예시

예시 1

입력

2
< >

출력

897
021

예시 2

입력

3
< < <

출력

6789
0123

예시 3

입력

3
> < <

출력

9678
1023